I ran into an interesting math puzzle while trawling the blag-o-sphere today.
One hundred students line up to walk by one hundred closed lockers. The first student walks by opening every locker that is closed. The second student then walks by and opens every second locker that is closed and closes every second locker that is open. The third student does the same for every third locker and the nth student does the same for every nth locker.
After all the students have walked by the lockers, how many lockers are open?
I thought about this for a while, but I was having some trouble visualizing what was happening. In the end, I decided to graph it to see what was happening. I wrote up a quick Processing sketch and looked at a smaller version of the problem. My smaller version had only ten lockers and ten people who run through them.
Once you’re looking at the picture, the answer the question is obvious. I’m not very satisfied with this method of solving the problem. It seems inelegant, and is purely a brute-force approach.
Another way to approach the problem is see if there is a closed form solution for any given door. If we had that, we could solve for the state of each locker and sum them up. Unfortunately, I think this comes down to a factoring problem. If the locker number has an even number of factors, then it is closed. If it has an odd number of factors, it is open. Interestingly, since most of the lockers remain closed it seems that most numbers have an even number of unique factors. That doesn’t really help explain the problem though.
So if I can’t find a closed form solution to the state of each locker, what other patterns can I see? By looking at the solutions for different numbers of lockers, I see that total number of lockers needed to give a certain number of opens follows some kind of power function. Looking at the first sixteen solutions shows that if I want n open lockers, then I need 2^n total lockers.
This is more like it. Now when someones asks about 100 lockers, I can find a solution quickly. What squared is 100? It’s 10 of course, so there are 10 open lockers after this sequence of events has been applied to 100 lockers. For any number, n, of lockers, the number of open lockers after n people have run though them is ?n rounded down.
So now I have my answer. I just need a reason. Why is it the case that the open doors follow this pattern? What that really boils down to after looking at it for a bit is the question: why are the only doors left open doors that are the square of a number? Does this mean that only square numbers have an odd number of unique factors?
Square numbers are the only numbers that have an odd number of unique factors because factors can come in pairs. With a square number, one of those pairs is made up of two of the same number, and in this situation that can only count as one toggle, not two.
So take locker number 10 for example. It has factors 1, 2, 5, 10. In this case 1 goes with 10 and 5 goes with 2. They cancel each other out and the locker stays closed.
The number 9, on the other hand, has factors 1, 3, 9. Here the 1 and the 9 cancel each other out, but the 3 doesn’t have anything to cancel it out. The locker remains open.
It turns out that getting sidetracked about closed form solutions for each individual door actually did provide the hint to understanding the problem.