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。
第 2/5 步：使用每轮线性映射
上一步下一步
通俗地说

看似无限的过程其实是有限线性动力系统。

T(x0,…,xn−1)=(y0,…,yn−1)T(x_0,\ldots,x_{n-1})=(y_0,\ldots,y_{n-1})
详细分析

该递推在含 2^n 个二进制状态的有限向量空间上定义线性映射 T。原过程是周期性坐标更新序列，其 n 步映射为 T。