Problem 6

There are

n

lamps

L_0,\ldots,L_{n-1}

in a circle, where

n>1

and

L_{n+k}=L_k

. At step

s_i

, if

L_{i-1}

is lit, switch

L_i

, otherwise do nothing. Initially all lamps are on. Show that (a) there is a positive integer

M(n)

such that after

M(n)

steps all lamps are on again; (b) if

n=2^k

, take

M(n)=n^2-1

; (c) if

n=2^k+1

, take

M(n)=n^2-n+1

Step 1 of 5: Encode the lamps

Previous step Next step

In plain words

Sequential updates make each lamp depend on the already updated predecessor.

x_i\in\mathbb F_2

Detailed analysis

Let $x_i$ be 1 when $L_i$ is lit and 0 otherwise. A switch is addition by 1 in the field with two elements. During one complete pass, the updated values satisfy $y_0=x_0+x_{n-1}$ and $y_i=x_i+y_{i-1}$ for $i$ from 1 through $n-1$ .