My father presented this surprising math puzzle to me when I was a kid. It begins with the city’s main street, which has 100 light poles numbered from 1 to 100, and 100 lamplighters, also numbered from 1 to 100. Initially, all the lights are turned off. Lamplighter #1 goes over the poles one after the other and reverses the state of the lights – if it’s on, he turns it off; if it’s off, he turns it on. Since all the lights are off initially, he turns all the lights on.

Next, lamplighter #2 goes over the poles that are multiples of 2 (2, 4, 6, 8, etc.) and reverses the state of the lights – if it’s on, he turns it off; if it’s off, he turns it on. At this stage, since all the lights were turned on by lamplighter #1, he turns off all the even-numbered light poles.

Then lamplighter #3 goes over the poles that are multiples of 3 (3, 6, 9, 12, etc.) and reverses the state of the lights. This step becomes a little more complicated, as some lights are off and some are on. The same method is followed by lamplighters #4 to #100; each lamplighter, n, reverses the state of light poles that are multiples of n.

Now, the question arises: which light poles are turned on after lamplighter #100 finishes?

The solution is related to whether the number of divisors a number has (including 1 and itself) is odd or even. If you’re not familiar with this puzzle, take some time to think about it before you scroll down. It’s not a complicated puzzle, but it’s sure to bring a smile to your face when you figure it out.

It’s Python time

lights = [False] * 101                             # False = off; True = on. Originally all lights are off
for lamplighter in range(1,101):                   # looping over 100 lamplighters
   for walk in range(lamplighter,101,lamplighter): # lamplighter walks in steps...
      lights[walk] = not lights[walk]              # ...and reverses the state of each light

for light in range(1,101):                         # let's see what lights are on
   if lights[light]:
      print(light)

Output

1
4
9
16
25
36
49
64
81
100

Interestingly, the answer contains only square numbers (1, 4, 9, 16, etc.). Have you figure out why?