Puzzle: Lockers

Problem: In a school common room there are 100 locker boxes. At tiffin, 100 students line up outside the common room. One by one, they come in. The 1st student opens every locker box. The 2nd student closes every even locker box. The 3rd student changes the state (opens if closed, closes if open) of every 3rd locker box. And so on. The nth student changes the state of every nth locker box.

After the 100 students have done their job, which are the locker boxes that remain open?

Solution: Consider locker numbers 3,4,6 as examples. Locker 3 is opened by 1st student and closed by the 3rd student and remains closed. Locker 4 is opened by 1st student, closed by 2nd student and reopened by 4th student. Locker 6 is opened by 1st student, closed by 2nd student, reopened by 3rd student and closed by the 6th student. So, out of these three, locker 4 remains open.

A locker number n will be accessed by all those students with number i where i is a factor of n. Consider only distinct pairs of factors of n i.e. only one pair out of (n1,n2) and (n2,n1). Therefore, for all such factor pairs (n1,n2) of n, one of them will open the locker and the other will close the locker. However, if n1==n2, then locker will remain in the open state. In other words, for all numbers n which are squares, the corresponding locker will remain open.

In this particular case with 100 lockers, only the lockers with numbers which are squares will remain open i.e. 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.