A million switches, a million light bulbs, a million passes. The question seems monumental, but it boils down to something much more intimate: the individual history of each light bulb.
The switches and the million light bulbs
Riddle statement
In a hallway there are a million light bulbs, numbered from 1 to 1,000,000. At first, they are all turned off.
A person walks down the hallway many times. In the first pass the state of all the bulbs changes. In the second, the state of the even bulbs changes. In the third, the state of the bulbs numbered with multiples of 3 changes. And so on: in the pass number k, the state of all the bulbs whose number is a multiple of k.
changes. After completing the 1,000,000th pass, how many bulbs remain on?
Show solution
Solution
Answer: Exactly 1000 bulbs remain lit: those that occupy perfect square positions.
Explanation:
The bulb $n$ changes state in pass $k$ if and only if $k$ divides $n$. Therefore, it changes as many times as it has positive divisors $n$.
When the number of changes is even, the light bulb ends up off (returns to its initial state). When it is odd, it ends up on.
Normally divisors come in pairs: if $d$ divides $n$, so does $n/d$, and they are both different. This always gives an even number of divisors.
The exception is perfect squares. In them there is a divisor $d$ such that $d = n/d$, that is, $d^2 = n$, which is not a pair with any other. That makes the total number of divisors odd, and the light bulb stays on.
Between 1 and 1,000,000 there are exactly 1000 perfect squares: