The Locker Problem

In a cavernous room at an army base stands a line of 1000 lockers. A soldier walks by and opens every one. A second soldier closes every second locker. A third soldier changes the state (either opens or closes) every third locker. This continues until the 1000th soldier either opens or closes the 1000th locker.

Which lockers are now open?

Hints
• For the first 10 lockers, figure out which are open. Is there a pattern?
• When does soldier a open or close locker n?

Solution
First note that the second soldier changes the state of lockers 2, 4, 6, etc., the third soldier does lockers 3, 6, 9, etc., and in general, soldier a opens or closes locker n if a divides n. So the lockers with an even number of divisors are closed, and the ones with an odd number of divisors are open. Which numbers have an odd number of divisors?

Consider locker 12. The divisors of 12 are 1 and 12, 2 and 6, 3 and 4. If we pair up the divisors so that their product is 12, it is easy to see that the number of divisors is even, so locker 12 is closed.

Now consider locker 16. Pairing up its divisors, we get 1 and 16, 2 and 8, 4 and 4. Since 4 repeats, the number of divisors is odd, and locker 16 is open.

When does divisor a repeat? When the square of a is n. So the open lockers are just the square numbers: 1, 4, 9, 16, 25, ...