Expert: Lynn Houston - 11/17/2008

Question
Famous Locker problem
Here is the famous locker problem: Imagine you are at a school that has 100 lockers, all shut.
Suppose the first student goes along the row and opens every locker.
2. The second student then goes along and shuts every other locker beginning with locker number 2.
3. The third student changes the state of every third locker beginning with locker number 3. (If the locker is open the student shuts it, and if the locker is closed the student opens it.)
4. The fourth student changes the state of every fourth locker beginning with number 4.
Imagine that this continues until the 100 students have followed the pattern with the 100 lockers. At the end, which lockers will be open and which will be closed? How do you know? How many lockers will be touched exactly two times? How do you know? How many lockers and which ones were tocuhed three times? How do you know? Which students touched both 36 and 48?


Answer
All the lockers will be open except those that are perfect squares (ie, 9, 16, 25, 36, 49, 64, 81, 100)

Here's the reasoning and you can figure out the rest of your questions based on this:

1) the lock will be open if its state would be changed odd amount of times, and will be closed if its state would be changed even amount of times.
2) If a number N is not a perfect square, when it has a fact p, it must have another fact q<>p, such that pq = N. Therefore, If a number is not a perfect square, it must have even numbers of factors.
3) If a number N is a perfect square, there must be a number r such that r^2 = N. Therefore, If a number is a perfect square, it must have odd numbers of factors.
4) Since there was not a person to come to changes the "state" for every locker, the factor "1" for every number does not corresponds to a state change.
5) Hence, if the lock number is not a perfect square, its state would be changed odd number of times, and the locker would be finally open, and vice versa.

Based on the above, only the "square" lockers would be touched twice (once for the sq rt and once for the number).  Lockers that would be touched 3 times are numbers that only have 3 divisors (not including 1).  6 = 2, 3, 6; 8 = 2, 4, 8; 10= 2, 5, 10; 14 = 2, 7, 14, etc)

divisors of 36 are 2, 18, 3, 12, 4, 9, 6, 36.
divisors of 48 are 2, 24, 3, 16, 4, 12, 6, 8, 48
Therefor ppl 2, 3, 4, 6 and 12 would touch both.