Which Doors are opened?

A certain building in a school has 100 doors. A student runs down the hall and opens each door. A second student runs down the doors and closes every other door. A third student runs down the doors and "changes the state" of every third door (i.e., if the door is open, he closes it; if it's closed, he opens it). This continues for 100 students -- the N-th student changes the state of each N-th door. After all 100 students have run through the doors, which doors are open? Why?


Answer:

In this situation it is easy to see that every door whose number is a perfect square will be open at the end of the exercise, and all other doors will be closed. For example the 18th door will be visited by those students whose numbers are factors of 18. i.e. by numbers 1,2,3,6,9,18. This is 6 students (an even number) and this means the door will in turn be open/closed/open/closed/open/closed. Now all numbers with an even number of factors will end up closed. And all numbers EXCEPT PERFECT SQUARES have an even number of factors if we include 1 and the number itself. For a perfect square, say 16, we have factors 1,2,4,8,16, an odd number, and the doors would be open/closed/open/closed/open. We conclude that all the doors whose numbers are perfect squares will be open at the completion of the exercise.