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 3 of 5: Prove the universal return

Previous step Next step

In plain words

Reversibility on the all-on orbit gives part (a), even if the map is not inverted on every state.

T^r(u)=u\text{ for some }r>0,\quad u=(1,\ldots,1)

Detailed analysis

Apply the recurrence backward to the particular orbit starting at the all-one vector. The same prefix-sum calculation reconstructs a unique predecessor on this orbit at every round; hence the orbit is a cycle, not a transient. Since there are finitely many states, some positive r returns u, giving M(n)=nr plus the appropriate partial pass.