MathLabs

第6题

圆周上有 nn 盏灯 L0,…,Ln−1L_0,\ldots,L_{n-1}，其中 n>1n>1 且 Ln+k=LkL_{n+k}=L_k。在步骤 sis_i 中，若 Li−1L_{i-1} 亮，则切换 LiL_i，否则不操作。初始时所有灯都亮。证明：(a) 存在正整数 M(n)M(n)，使得经过 M(n)M(n) 步后所有灯再次点亮；(b) 若 n=2kn=2^k，可取 M(n)=n2−1M(n)=n^2-1；(c) 若 n=2k+1n=2^k+1，可取 M(n)=n2−n+1M(n)=n^2-n+1。
第 3/5 步：证明一般回归
上一步下一步
通俗地说

只需全亮轨道上的可逆性即可得到 (a)，不必在所有状态上求逆。

Tr(u)=u for some r>0,u=(1,…,1)T^r(u)=u\text{ for some }r>0,\quad u=(1,\ldots,1)
详细分析

对从全 1 向量开始的轨道反向使用递推。同样的前缀和计算在每轮唯一重建该轨道上的前驱，因此轨道是循环而非暂态。状态有限，故存在正整数 r 使其回到 u，取 M(n)=nr 加上适当的不完整轮次即可。