The Locker Problem

 "

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?

"

My first thought is to imagine that all of the lockers are labelled starting at 1 and going to 1000. Then I consider one of the lockers and watch for when it gets opened or closed. This leads me to find that a locker will get 'toggled' if the student's turn # divides the locker number. Hence, over the course of the whole process that locker will get toggled a number of times equal to the count of its natural divisors. If a locker number has an even number of divisors it will end up open and if it has an odd number of divisors it will end up closed. The question then is: "Which natural numbers have an even/odd number of divisors?"

Now I begin thinking of some small examples to maybe get an intuition.

Locker #: (divisors, ...) open/closed

1: (1) closed

2: (1,2) open

3: (1,3) open

4: (1,2,4) closed

5: (1,5) open

6: (1,2,3,6) open

7: (1,7) open

8: (1,2,4,8) open

9: (1,3,9) closed

10: (1,2,5,10) open

11: (1,11) open

12: (1,2,3,4,6,12) open

 

Based on these first couple I thought that the primes might have something to do with it because they are always open. However, I quickly began to see that the only lockers that end up closed are square number lockers and all other lockers end up open.

Now I will try to think of a reason why this might be the case. First off, we can count the number of unique divisors of a number using combinatorics. Let p_q(n) be the power of a particular prime q in the prime factorization of n. If we are constructing a divisor of n then we can choose to include between zero and p_q(n) of each prime factor of n. So the number of divisors is given by \Prod_{prime q} (1+p_q(n)) For a square number, p_q(n) is always even so each term in the product, and thus the whole product, is necessarily odd. This means that it is true that all of the square numbered lockers will end up closed. But we aren't done because we also have to show that all of the non-square number lockers end up open. A non-square number must have at least one prime factor with a power that is odd which means that at least one of the terms in the divisor counting product will be even, and thus the whole product will be even. This shows that the non-square lockers will all end up open.

 

Now if I wanted to spend more time thinking this through I might try to figure out a simpler argument that doesn't involve prime factorization.