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 2 of 5: Use a linear round map

Previous step Next step

In plain words

The infinite-looking process is a finite linear dynamical system.

T(x_0,\ldots,x_{n-1})=(y_0,\ldots,y_{n-1})

Detailed analysis

The recurrence defines a linear map T on the finite vector space of 2^n binary states. The original process is the periodic sequence of coordinate updates whose n-step map is T.