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?