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 4 of 5: Evaluate the power-of-two case

Previous step Next step

In plain words

Frobenius squaring over F_2 makes powers of two collapse the recurrence.

n=2^k\Longrightarrow M(n)=n^2-1

Detailed analysis

For n a power of two, repeatedly square the prefix-sum recurrence over F_2. The binomial coefficients between the endpoints vanish in pairs, and the coordinate-update word reduces to the identity after n^2-1 updates on u. Thus the stated value is valid.