Twenty bored students take turns walking down a hall that contains a row of closed lockers, numbered 1 to 20. The ﬁrst student opens all the lockers; the second student closes all the lockers numbered 2, 4, 6, 8, 10, 12, 14,16, 18, 20; the third student operates on the lockers numbered 3, 6, 9, 12, 15, 18: if a locker was closed, he opens it, and if a locker was open, he closes it; and so on. How many lockers remain open after all the students finish?
Table Of Content
This is actually a simple problem after considering Divisors of Perfect Squares.
1. Reducing the problem into an instance of counting divisors
From the definition of the problem, we can gather that student can only open lockers that are multiples of . This naturally suggests that locker will be operated on by student if and only if is a multiple of . This can be easily proven.
Locker will be operated on by only when is a multiple of
By definition, will be operated on by if some multiple of becomes . Similarly, when is a multiple of , then student will have to operate on locker .
Because only only divisors of will touch the locker, then it’s clear that the number of times locker gets operated on is the number of divisors of .
2. Only lockers that are perfect squares remain open
Naturally, if a locker is operated on for an even number of times, it remains closed, because there are an integer sequence of opening-then-closing that locker. Similarly, if a locker is operated on for an odd number if times, it will become open.
Because the number of times the locker is operated on is the number of divisors of , then only those lockers with odd number of divisors can remain open. As we’ve proven previously, only perfect squares have odd divisors, hence only the perfect squared lockers remain open in the end.