Lockers

[snipez90]

A certain hallway contains a row of lockers numbered from 1 to 30. All the lockers are initially closed. 30 students are lined up in the hallway. The first student walks down the row and opens up all the lockers. The second student closes all the lockers numbered 2, 4, 6, ..., 30. The third student performs an operation on the lockers numbered 3, 6, 9, ..., 30; if a locker was open, he closes it and if a locker was closed, he opens it. For the n-th student, he operates on the lockers numbered by multiples of n; if a locker was open, he closes it and if a locker was closed, he opens it. How many lockers remain closed after all 30 students finish their walks?

[jimmysnyder]

Answer:

24

Proof: (sorry, I don't know how to hide the proof)


oooooooooooooooooooooooooooooo
c c c c c c c c c c c c c c c
c o c o c o c o c o
o o c o o c o
c o o c c c
c o c o o
c o o c
c c c
o o o
c o c
c o
c o
c o
c o
c o
o
c
c
c
c
c
c
c
o
o
c
c
c
c
c

[D H]

25.

Door number n will be closed if n has an even number of divisors, and open if n has an odd number of divisors. The divisor function phi0(n) is odd iff n is a perfect square. Since there are five perfect squares between 1 and 30, there will be five open doors when all students finish their tasks. The other 25 doors will be closed.

[Diffy]

When I first saw this problem it was asked with 1000 lockers, it still really easy to figure out with that number, but initially it makes it sound harder.