Puzzle Toad-2 Lights of the Round Table

Puzzle Toad-2 Lights of the Round Table and Solution #

题目翻译 #

King Arthur 正在准备圆桌会议, 圆桌的座位编号为 $1, 2, …, n$ , 每个座位前面都有一盏台灯. 当 King Arthur 走进圆桌所在的房间里时, 他发现有些台灯被人关了. 作为国王, King Arthur 不能仅仅直接把熄着的灯打开, 他得命令别人做这件事. 因此, King Arthur 需要在纸条上写好座位的编号, 然后让仆人去按下座位前台灯的开关按钮. 这场会议是讨论驱逐 Merlin 的, 并且只有当所有的台灯都亮着时, 会议才能开始. 通过水晶球, Merlin 可以看到 King Arthur 在纸条上写下的内容, 并且在仆人到达桌子前旋转圆桌, 以便阻止灯到达全部亮起的状态. 仆人可不能自己行事, 违背 King Arthur 的意图是要杀头的. 在什么样的情况下, 无论初始状态如何, King Arthur 总是能够通过下达合适的指令来使得会议顺利进行呢?

解答 #

必胜情况 #

如果 $n = 1$ , 显然 King Arthur 是必胜的; 如果 $n = 2$ , King Arthur 也是必胜的. 如果灯一亮一灭, King Arthur 让仆人按下任一开关都能把灯变为全灭或全亮的状态 (可以看作化归成了 $n = 1$ 的情况) . 事实上, 当 $n = 2^k$ 时, King Arthur 都是必胜的. 我们下面给出两种证明方法.

归纳证明 #

$n = 1$ 时显然有必胜策略. 假设对于 $n = 2^k$ , King Arthur 拥有必胜策略. 考虑 $n = 2 ^{k + 1}$ , 我们把 $i$ 和 $i + 2^k$ 两盏灯看作一盏 “超级灯” , 定义只有当这两盏灯的状态相同时, 超级灯才亮. 显然对于 $1, 2, …, 2^k$ 中的灯操作等价于对超级灯进行操作. 由归纳假设, 对于这 $2^k$ 栈超级灯, King Arthur 可以安排仆人把它们全部打开. 此时根据超级灯的定义, $i$ 和 $i + 2^k$ 都亮或者都灭. 重新定义只有当两盏灯都亮时, 超级灯才亮. 这时, King Arthur 对于 $i$ 和 $i + 2^k$ 同时下达的命令相当于对超级灯下命令. 由归纳假设, 对于这 $n$ 栈重新定义的超级灯, King Arthur 可以把它们全部打开, 这时全部的 $2^{k + 1}$ 栈灯也就都亮了. 综上, $n = 2^k$ 时, King Arthur 拥有必胜策略.

代数证明 #

上面的证明对于一位中世纪的君王来说有些过于精妙而复杂了. 如果 King Arthur 每次都只让仆人把现在亮着的灯都关了, 能否到达一个所有的灯都熄灭的局面, 以便最后一轮全部打开呢? 这种简单的策略在 $n = 2^k$ 时竟然也是凑效的. 下面我们来证明这一点. 用状态多项式 $b(x) = b_0 + b_1x + … + b_{n - 1}x^{n - 1}$ 记录 $n$ 个灯的状态. 其中 $b_i$ 考虑模 $2$ 后的数值, $x^i$ 考虑幂次模 $n$ 再 $+1$ 后的数值 (即 $x^{n + i}$ 与 $x^i$ 相同). 如果 $b_j$ 为奇数代表灯亮, 为偶数代表灯灭. King Arthur 让仆人把当前亮着的灯都关掉, 在模 $2$ 意义下相当于把 $b_i$ 中为 $1$ 的变为 $0$ , $b(x) \leftarrow b(x)(1 + x^0)$ 恰好可以代表这一过程; 而 Merlin 把桌子旋转 $j$ 位相当于把 $(1 + x^0)$ 修改为 $(1 + x^j)$ , 即对 $x^i$ 施加的操作会影响 $x^{i + j}$ . 假设初始的状态多项式为 $t(x)$ , 经过 $m$ 轮操作后的状态多项式为 $$ t(x)\prod_{t = 1}^{m}(1 + x^{j_t}) $$ 其中, $0\leq j_1, j_2, …, j_m\leq n - 1$ . 假设 $m \geq n(n - 1) + 1$ , 根据抽屉原理, $\exist 0\leq i\leq n - 1$ , 满足 $i$ 在 $j_1, j_2, …, j_m$ 中出现了至少 $n$ 次. 下面我们单独计算旋转 $i$ 位造成的影响. 旋转 $2$ 次, 有 $$ (1 + x^i)^2 = 1 + x^i + x^i + x^{2i} = 1 + x^{2i} $$ 重复这一步, 有 $$ (1 + x^i)^{2^p} = 1 + x^{2^pi} $$ 令 $p = k$ , 则 $2^p = 2^k = n$ , 有 $$ (1 + x^i)^n = 1 + x^{ni} = 1 + 1 = 0 $$ 故经过 $m\geq n(n - 1) + 1$ 轮操作后, 由于 $(1 + x^i)^n = 0$ 的影响, 状态多项式 $t(x)\prod_{t = 1}^{m}(1 + x^{j_t}) = 0$ , 所有灯全灭. 在下一轮, 所有灯能够全亮, King Arthur 是必胜的.

必败情况 #

当 $n \not = 2^k$ 时, King Arthur 都是必败的. 先考虑比较简单的情况: $n$ 为奇数. 如果 $n$ 为奇数且初始状态不为全亮或全灭, 一定存在相邻的两盏灯, 它们恰好为一亮一灭. 由于 $n$ 为奇数, 所以无论 King Arthur 怎样下达命令, 都会存在相邻的两个位置都被选到了或者都没被选到, Merlin 要做的就是把把桌子一亮一灭的两盏灯转到这两个位置. 通过这种操作逻辑, Merlin 总是能够保证有两盏灯一亮一灭, 从而无限期地拖延会议. 对于不为 $2$ 的幂次的偶数 $n$ , $n$ 可以写成 $2^k \times m$ , 其中 $m$ 是奇数. 把间隔 $2^k$ 的灯放到一组, 把 $n$ 拆分成 $2^k$ 组分别考虑, 每一组都是 $m$ 个. 如果存在一组灯中两盏灯一亮一灭, 对这一组灯套用奇数时的处理策略即可.