The bulbs in a ring that always come back on

Question

Bulbs numbered 1 to n are arranged in a ring, all initially on. At step t (for t = 1, 2, 3, ...) you look at bulb number t (counting round the ring, so bulb n is followed by bulb 1). If bulb t is on, you toggle bulb t + 1 (turn it off if on, on if off). If bulb t is off, you do nothing. Then you move on to step t + 1.

Prove that, whatever n is, at some later step all the bulbs are on again.

Accepted Answer

The process is deterministic, has finitely many states, and every step is reversible. A reversible process on a finite set must return to its starting state. Finitely many states, so eventually a repeat. Group the steps into rounds of n (one full pass round the ring). The state at the end of a round is a function of the state at the start of that round; call this function F. There are only 2 to the n possible states, so the sequence of end-of-round states must eventually repeat some state, after which it cycles. Each step can be undone. Suppose you know the state of all bulbs after step t. St…

The bulbs in a ring that always come back on

Your answer

Discussion

Learn the concepts

Related questions