I'M LOCKED! Well if that was so it would make the problem a lot easier.
Logic wise we know that each student visits each locker they are a factor of. Each factor for a locker number would change the state of the locker. An odd number changes the state to a new one, an even number of factors keeps the state of the locker as its original state. The closed lockers have odd factors as we start with open lockers, the even ones have open lockers.
My approach to this problem was to start out with a brute force method of the first 17 lockers to look for any patterns. The pattern I noticed was that it seemed to be that the first locker is closed, then 2 lockers are open, then a closed one, then 4 open, then 1 closed, 6 open, etc. So there seemed to be a pattern where the closed lockers were separated by increments of the sequence 2,4,6,8,...,100,102,..,2n, where n is a natural number.
From this I wanted to make a recurrence relation for the closed lockers. The sequence for closed lockers is 1,4,9,16,25,36,... . This sequence has the recurrence relation K_n = K_(n-1) +2n + 1, where n is a natural number. I solved this recurrance relation for a closed form solution, giving h_n = n^2+2n+1 where h_0 = 1, and n is a natural number. Using this we can find all closed lockers, for a sequence of any length. Example n = 3, h_30 = 961. The factors of 961 are 1, 31, 961, which is an odd number, so it is in fact closed. Doesn't quite prove my relation, but it's close enough of a proof for this assignment. So I could give a list of all the 31 closed lockers (as n starts at 0) in the first 1000 lockers. 31 closed, thus 969 open lockers.
Looking through the keyhole I realize I've been quite silly and the answer is simply all the perfect squares. This makes sense as if you simply the closed form solution it gives h_n = (n+1)^2. The explanation is that when we find the factors of a number, they come in pairs. For example, for 30 our pairs are, 1x30, 2x15, 3x10, 5x6. That's 8 factors. The only way to get an odd number of factors is to get factor that pairs with itself, for 9, 1x9, 3x3, thus an odd number.
A silly answer, and a more straightforward one. At least the doors unlocked now...
Your response reminds me of my own students and their thinking. Some find the direct route to the solution, they don't stray far from the path; whereas others like to take the scenic route. Do you think there is value in encouraging your students to explore both ways of deriving a solution, even when it makes them uncomfortable? What strategies will you employ?
ReplyDelete