第6题

圆周上有

n

盏灯

L_0,\ldots,L_{n-1}

，其中

n>1

且

L_{n+k}=L_k

。在步骤

s_i

中，若

L_{i-1}

亮，则切换

L_i

，否则不操作。初始时所有灯都亮。证明：(a) 存在正整数

M(n)

，使得经过

M(n)

步后所有灯再次点亮；(b) 若

n=2^k

，可取

M(n)=n^2-1

；(c) 若

n=2^k+1

，可取

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

。

第 5/5 步：计算比 2 的幂多一的情形

上一步下一步

通俗地说

增加一个坐标使消去次数恰好改变 n−2。

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

详细分析

同一递推现在多一个循环坐标，两个端点发生一次重叠。反复平方计算表明全 1 状态恰在 n^2−n+1 步后恢复，此时所有比特再次为 1。这证明第二个上界。