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。
第 1/5 步：编码灯状态
上一步下一步
通俗地说

顺序更新使每盏灯依赖于已经更新的前一盏灯。

xi∈F2x_i\in\mathbb F_2
详细分析

令 LiL_i 亮时 xix_i 为 1，灭时为 0。在二元域中切换就是加 1。一整轮后 y0=x0+xn−1y_0=x_0+x_{n-1}，且 ii 从 1 到 n−1n-1 时 yi=xi+yi−1y_i=x_i+y_{i-1}。