## Light Bulbs in a Circle

[Winkler] Light bulbs placed on a circle are numbered 1 through N, all initially on. At time t, you examine bulb number t, and if it's on, you change the state of bulb t+1 (mod N); i.e., you turn it off if it's on, and on if it's off. If bulb t is off you do nothing. Prove that if you continue around and around the circle in this manner, eventually all the bulbs will again be on.

The applet allows you to experiment with the problem. Orange circles impersonate the on state of the bulbs, the red ones the off state. The green arrow points to the bulb under examination. The blue arrow points to the bulb whose state is going to be affected.

The applet generalizes the problem in two ways. First of all, the look ahead may be an integer other than 1; i.e., the examination of bulb t may affect bulb t+L, L > 0, where L is the "look ahead" parameter, 1 originally. Secondly, instead of examining the bulbs in their natural order, you may skip a chosen number (S) of bulbs.

What if applet does not run? |

### References

- P. Winkler,
*Mathematical Puzzles: A Connoisseur's Collection*, A K Peters, 2004, pp. 81-82 (Light bulbs in a circle)

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

In the original problem, N is arbitrary,

The process is reversible: a state of affairs at time t is uniquely determined by that at time t+1.

Since the number of possible states is finite, the process is bound to enter a loop by the Pigeonhole principle.

The generalization does not require special treatment, but makes it obvious that there is one special case, viz., the state wherein all the bulbs are off. Except when

Starting with all the bulbs on, it is impossible to reach a dead end combination where all the bulbs are off.

Indeed, to turn off an apparently last bulb, one would have to be examining a bulb that is on. This logic does not apply when

Now for the proof.

Because the number of states is finite, state repetition is bound to happen. Assume at time t_{1} a state is repeated for the first time. Assume also, that the repeated state has occurred at time _{0} < t_{1}._{0} = 0._{1}-1 and t_{0}-1 are also the same, which would contradict our assumption that a repetition occurred for the first time at time t_{1}.

|Activities| |Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71945699