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。
第 4/5 步：计算 2 的幂情形
上一步下一步
通俗地说

F_2 上的 Frobenius 平方使 2 的幂情形递推崩缩。

n=2k⟹M(n)=n2−1n=2^k\Longrightarrow M(n)=n^2-1
详细分析

当 n 为 2 的幂时，在 F_2 上反复平方前缀和递推。端点之间的二项式系数成对消去，坐标更新词在 u 上经过 n^2−1 步缩减为恒等。因此给定值有效。