A school has 1,000 students and 1,000 lockers. On the first day of school, all the lockers are open.
Student #1 closes each locker.
Student #2 opens each second locker.
Student #3 changes the state of each third locker (i.e. opens them if they are closed, or closes them if they are open)
...and so on, until all 1,000 students have had their turn.After all 1,000 lockers are done, which lockers are open? Which are closed? Why?
This is the puzzle we have been assigned to work on. Now, I was shown this problem before in grade 11, so I can't say exactly how I figured it out this time around.
A very common strategy for solving complex math problems is to somewhat tone down the complexity of the problem. In this case, we have 1000 lockers to work with. Quite a few. Instead, I worked with a smaller case to try and notice any patterns. Go through just ten lockers and run the algorithm. What was the result? It turns out that locker 4 and locker 9 are closed. Interesting. What about twenty lockers? Then lockers 4, 9 and 16 are closed. I hypothesise that perfect square numbers remain open in this puzzle scenario.
Why is that? If we break down the problem a bit more, we note that the lockers are in a binary state, open or closed. This is further determined by how many students have interacted with each locker; an even number of interactions opens the door, while odd closes.
The arithmetic suggests that each n'th student will interact with each np'th locker, where p is another natural number and np≤1000. Or perhaps simpler, any student assigned a number will only interact with lockers that are a multiple of their assigned number.
After breaking down the problem like this, the question becomes much more concise: which numbers 1-1000 have an odd number of factors? Which have an even number?
The factors of a number will always be a set of pairs, two distinct numbers that multiply to give the original - except when the number is a perfect square! In the case of 4, 9, 16, etc. one of their factoring pairs will have two of the same number.
Hence, by only working out the first 20 lockers, we have determined the pattern for all 1000 lockers.