MathLabs

Problem 6

There are nn lamps L0,…,Ln−1L_0,\ldots,L_{n-1} in a circle, where n>1n>1 and Ln+k=LkL_{n+k}=L_k. At step sis_i, if Li−1L_{i-1} is lit, switch LiL_i, otherwise do nothing. Initially all lamps are on. Show that (a) there is a positive integer M(n)M(n) such that after M(n)M(n) steps all lamps are on again; (b) if n=2kn=2^k, take M(n)=n2−1M(n)=n^2-1; (c) if n=2k+1n=2^k+1, take M(n)=n2−n+1M(n)=n^2-n+1.
Step 5 of 5: Evaluate the one-more-than-a-power case
Previous stepNext step
In plain words

Adding one coordinate changes the cancellation count by exactly n-2.

n=2k+1⟹M(n)=n2−n+1n=2^k+1\Longrightarrow M(n)=n^2-n+1
Detailed analysis

The same recurrence, now with one extra cyclic coordinate, has one endpoint overlap. The repeated-squaring calculation leaves exactly n^2-n+1 updates on the all-one state, after which every bit is again 1. This proves the second stated bound.