TOAD 2 - Lights of the Round Table
呼啦啦准备翻译完 TOAD 。这些题真心虐心啊……
今天说的这个题有一个众所周知的方法。但是还有一个非常漂亮的解法，我相信还是没多少人见过的。
Problem
有 \(n\) 个人坐在一张圆形桌子前，每个人面前有一盏灯。现在 A 和 B 博弈。流程如下：
- A 选择若干个位置，并把选择的结果告诉 B
- B 把桌子转一下
- 把 A 选择的位置的灯的状态同时取反
- 重复以上过程
游戏终止的条件是存在某一时刻，使得所有的灯都是亮的。游戏终止则 A 获胜，否则 B 获胜。
A 随时可以调整策略，即 A 每次决策的时候可以看到现在灯的状态，并做出反应。
问：什么情况下 A 可以获胜。
Solution
结论：当 \(n\) 为 2 的整数次幂或者初始局面灯的状态全部相同时 A 可以获胜，否则 B 一定获胜。
第二种情况的证明是显然的，我们主要讨论第一种情况的证明。
第一种方法
用数学归纳法。
\(n = 1\) 时，显然。如果初始是亮的就赢了否则把它的状态取反即可。
如果 \(n = 2^k\) 时具有获胜策略，我们要证明 \(2n\) 个人也一定有必胜策略。
我们把灯一次编号为 \(1, 2, \dots, 2n\) ，并把这 \(2n\) 盏灯分成 \(n\) 组： \(i\) 和 \(i + n\) 分为一组。
我们把每一组看成是一盏超级灯。我们现在定义超级灯是亮的，当且仅当这一组的两盏灯的明灭状态相同。现在我们有 \(n\) 盏超级灯，每一次我们可以改变若干盏超级灯的状态，因为改变一盏超级灯的状态只需要改变这一组内任意一盏灯的状态即可。由于对于 \(n\) 盏灯我们有必胜策略，因此我们总可以把这 \(n\) 盏超级灯的状态变为全亮。
现在这 \(n\) 盏超级灯的状态全亮了，但是可能有若干盏超级灯代表的两盏灯都是灭的。我们重新定义超级灯是亮的，当且仅当这两盏灯都是亮的。每一次改变超级灯状态的时候，我们总是会把这两盏灯的状态同时改变，因此这两盏灯的状态总是相同的。我们再次利用 \(n\) 时的必胜策略即可。
第二种方法
这种方法听起来很不可思议，但是它确实是可行的……
现在要求灯是全亮的。我们不妨要求灯全灭，最后再一次操作把所有灯反过来就好了。于是 A 的目标是把所有灯灭掉。A 的策略很简单：每次选定当前亮着的所有的灯。
我们来证明这是可行的。定义一个多项式 \(b(x) = a_0 x^0 + a_1 x^1 + \dots + a_{n - 1} x^{n - 1}\) ，其中 \(a_i\) 表示第 \(i + 1\) 盏灯的明灭状态。我们不妨设这一次 B 选择把桌子顺时针旋转 \(j\) 个位置，那么这次操作相当于给多项式 \(b(x)\) 乘上一个 \(1 + x^j\) 再 \(\bmod (x^n - 1)\) 。（把所有的操作看成是在 \(GF_2\) 下的吧）
经过 \(m\) 次操作后，现在的多项式为
\[t(x) \equiv b(x) \prod_{i = 1}^m (1 + x^{j_i}) \mod (x^n - 1).\]
当 \(m \geq n(n - 1) + 1\) 时，我们知道至少有 \(n\) 次操作，这 \(n\) 次操作选择的 \(j\) 是相同的。
对于任意一个 \(j\) ，在 \(GF_2\) 内我们有
\[(1+x^j)^2 = 1 + 2 x^j + x^{2j} = 1 + x^{2j}.\]
由于 \(n\) 是 2 的整数次幂，于是
\[(1+x^j)^n = 1 + x^{nj} = 1 + x^0 = 0.\]
所以 \(t(x)\) 一定为 0 ，表示所有的灯都灭了。
无解
考虑 \(n\) 为大于 1 的奇数的情况。如果初始状态不是全部相同，则一定有两盏相邻的灯它们的状态不相同。我们保证任意时刻这两盏灯的状态均不相同即可。
对于 A 的每次操作，由于 \(n\) 是奇数，因此必定存在相邻两个位置，对这两个位置的操作是相同的。B 只需转一转，把这两个位置与两盏灯对应起来即可。
延伸一下，对于 \(n = 2^a * b\) 其中 \(b\) 为大于 1 的奇数，那么我们把这 \(n\) 盏灯分为 \(2^m\) 组，每组 \(b\) 个。保证一组内整个游戏就肯定无解。