Lockers Problem (and Solution)

November 8, 2011


The inspiration for this entry came from a question posed on The Daily WTF. To paraphrase: there are 100 lockers, all closed, and one needs to 'toggle' (logical NOT - if it is open, close it, otherwise open it) each nth locker for n from 1 to 100. So for instance, first n=1 so toggle lockers (1,2,3,4...100) so all are open. Next n=2, so toggle (2,4,6,8...100) so all odd-numbered ones are open and all even-numbered ones closed. Then n=3 so toggle (3,6,9...99), etc, up to n=99 so toggle (99), and finally n=100 so toggle (100).

What lockers remain open after this is done? Brute force / counting methods are not allowed. I would say no programming allowed also.


A possible way to arrive at a solution is described below (that was a spoiler alert).

It took me a while to get the basis of this problem. First I made a few observations:

Now it becomes more challenging. The problem is now reduced in half but still not obvious to solve. To move further towards abstracting the problem I began with a simpler system of 10 lockers and increased the number from there:

This is sufficient grounds for a solution. If all unique factors, including 1 and the number itself are considered, what feature determines whether the number of factors is odd or even? It looks like this would be dependent on repeat factors - with two repeat factors for instance, one factor will not be included in the list thus making the total number of factors odd. For instance, factors of 4 are 1,2,4, while for 10 they are 1,2,5,10 since 4 has 2 as a repeat factor.

Now the problem is to generalize that description to a certain number set. By a proof that is left to the reader, it can be seen that this is true only for square numbers. Thus, lockers 1,4,9,16...81,100 will be open, while the rest will be closed (initial state).

Programmatic Solution and Graph

To confirm the solution, I generated a brute-force program that displayed the results of each step of the algorithm performed on 700 lockers (note that since the number of lockers does not affect the solution set, this presents valid solutions for all variations of this problem from 1 to 700 total lockers). Here, a dark pixel 0x000000 represents an open locker and 0xFFFFFF represents a closed locker. The first row of pixels in the image is the result of toggling every locker, the second row is toggling every 2nd locker based on the results of the 1st row, and so on. The last row represents the solution to the problem with 700 or less lockers. The open lockers are indeed those that are numbered as perfect squares. The diagonal line trend is easily explained by the property that additional lockers do not affect the initial solution set, so the lockers that end up being open after a certain amount of operations remain open forever (the downward lines from the diagonal represent this). Note also that the graph confirms the idea that the overall effect of the upper half of the operations (n=351 to 700) simply reverses the state of the second half of the lockers. There is an interesting pattern occurring in the first few rows, that seems to have a nontrivial expansion. This is likely based on the prime-factor nature of each number - locker numbers with more total prime factors get 'toggled' relatively more, and since the distribution of factors seems to be stochastic this pattern appears similarly so.