Light Bulbs in a Circle (an Interactive Gizmo)

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.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

Solution

References

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

In the original problem, N is arbitrary, L = 1, S = 0. Except when S is a multiple of N -- S = 0 (mod N), Winkler's solution works without change. The solution is based on two observations:

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 S = 0 (mod N), this state is unreachable:

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 S = 0 (mod N), because then the bulb to be turned off is exactly the bulb being examined.

Now for the proof.

Because the number of states is finite, state repetition is bound to happen. Assume at time t₁ a state is repeated for the first time. Assume also, that the repeated state has occurred at time t₀ < t₁. We want to show that t₀ = 0. If it were not so, we could reverse one step and verify that the states at times t₁-1 and t₀-1 are also the same, which would contradict our assumption that a repetition occurred for the first time at time t₁.

Related material Read more...

	Six integers out of 10: Pigeonhole Principle

	Pigeonhole Principle (Same sum)

	Pigeonhole in a Matrix

	Pigeonhole in Calendar

	A nice puzzle modeled on the Petersen graph

	Proizvolov's identity in a game format

	Pigeonhole with Disjoint Intervals

	All antichains

	Euclid via Pigeonhole

	Light Bulbs in a Circle (an Interactive Gizmo)

	Seven integers under 127 and their Ratios

71945699