Q: In a hallway lined with 100 closed lockers, you begin by opening every locker. Then you close every second locker. Then you go to every third locker and open it (if it's closed) or close it (if it's open). Then you reverse every fourth locker, fifth, sixth , etc. Continue reversing every nth locker on pass number n. After 100 passes, where you toggle only locker #100, how many lockers are open?
A: There are 10 lockers open -- #1, 4, 9, 16, 25, 36, 49, 64, 81, and 100 -- all perfect squares.
This problem is based on the factors of the locker number.
Think about factor pairs. A number like 10 has two factor pairs, 1 and 10 and 2 and 5. But a number like 9 has only 1 unique factor pair of 1 and 9 because the other factor pair is 3 and 3. So 10 has four factors while 9 has only three.
Each locker is toggled by each factor; for example, locker #10 is toggled four times -- on pass numbers 1, 2, 5,and 10. Locker #40 is toggled on pass numbers 1, 2, 4, 5, 8, 10, 20, and 40. That's eight toggles: open-closed-open-closed-open-closed-open-closed.
The only way a locker could be left open is if it is toggled an odd number of times. The only numbers with an odd number of factors are the perfect squares. Thus, the perfect squares are left open.
For example, locker #9 is toggled on pass number 1, 3, and 9 (three toggles): open-closed-open.
