One Thousand Lockers Solution

If you draw out a scenario of 10 lockers it may be easier to see.  The first locker changes only once.  The second changes twice.  The third locker changes twice: the first person and the third.  The fourth changes from the 1^st, 2^nd and 4^th person.  What you begin to see is that most numbers can be factored an even number of times:  2*1, 1*2; 1*3,  3*1; 5*1, 1*5; 1*6, 2*3, 3*2, 6*1.  However, numbers that are perfect squares can also be factored as the square: 1*4, 2*2, 4*1; 1*9, 3*3, 9*1.  Only numbers with perfect squares change state an odd number of times.  So, what is the largest perfect square under 1000?  It is 31.  Thus, 31 lockers change state.

Back