A warden oversees an empty prison with 100 cells, all closed. Bored one day, he walks through the prison and opens every cell. Then he walks through it again and closes the even-numbered cells. On the third trip he stops at every third cell and closes the door if it’s open or opens it if it’s closed. And so on: On the nth trip he stops at every nth cell, closing an open door or opening a closed one. At the end of the 100th trip, which doors are open?
|
SelectClick for Answer |
Consider some representative cells. The warden stops at cell 7 twice, on the first and seventh trips. The divisors of 7 are 1 and 7. He stops at cell 10 four times, on the first, second, fifth, and tenth trips. The divisors of 10 are 1, 2, 5, and 10. Each door receives a quantity of visits equal to its number’s divisors.
All integers except perfect squares have an even number of divisors. So after 100 trips, only the doors whose numbers are perfect squares will remain open: cells 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100.
|
