A school has 1,000 students and 1,000 lockers, all in a row. They all start out closed. The first student walks down the line and opens each one. The second student closes the even numbered lockers. The third student approaches every third locker and changes its state. If it was open he closes it; if it was closed he opens it. The fourth student does the same to every fourth locker, and so on through 1,000 students. To illustrate, the tenth locker is opened by the first student, closed by the second, reopened by the fifth, and then closed by the tenth. All the other students pass by the tenth locker, so it winds up being closed. How many lockers are open?
The answer is
The nth locker is opened or closed by student number k precisely when k divides n. So if student k changes locker n, so does student n/k. They cancel each other out. This always holds unless students k and n/k are precisely the same person. That is, k = n/k. The lockers that are exact squares will remain open. These are lockers 1, 4, 9, 16, 25, etc. How many of these are there in a row of 1,000? You can go all the way up to 31×31 = 961, hence there are 31 lockers open.
No comments:
Post a Comment