The Locker Problem
A new school is being opened. The school has exactly 1000 lockers and 1000 students. On the first day of school, the students meet outside the building and agree on the following plan: The first student will enter the school and open all of the lockers. The second student will enter and close every locker with an even number. The third student will then "reverse" every third locker; that is, if the locker is closed, he will open it; if its open,he will close it. The fourth student will then "reverse" every fourth locker; and so on until all 1000 students in turn have entered the building and "reversed" the proper lockers. Which lockers will finally remain open?
I thought up what seemed to be the answer fairly quickly, but it was a little longer before I came up with a decent reason why it was true.
1) Any number can be written uniquely as a product of prime numbers
2) Let's ignore the first person who opens every door, and we might as well start with them all open.
We can look at the problem in cases:
Case 1 - The door has no duplicated factors
Lets take a locker number that is made of 2 primes eg. 6 = 2x3
This will have person 2, 3, and 2x3 changing it so it will be closed.
Now if we add another factor onto it eg. 30 = 2x3x5
We will have all the same people changing this door (+3), the product of the new factor with the people from before (+3), and the new factor itself (+1). It is a little confusing but you can see in this way there still has to be an odd number of people, and so this will also be closed.
Case 2 - The door has a duplicated factor but another as well
eg. 12 = 2²x3
This will have person 2,3,2x2,2x3,2x2x3 changing it so it will be closed.
Now add another factor again eg. 60 = 2²x3x5
Again this will have all the people from before (+5), the product of the new factor and the people from before (+5), and the new factor (+1). Again an odd number, so closed.
Case 3 - The door only has 1 factor
This will only have person 3,9 changing it so it will be open.
Adding another factor eg. 27 = 3³
This will only give you 1 extra person (person 27) so now the door is closed.
This pretty much shows that the only doors left open are square numbers.