Spinning Switches

题目

四个完全相同、没有标签的开关串联接到一只灯泡上。

这些开关都是简单的按压式按钮：你看不出它们当前是开还是关，但每按一次，该按钮的状态就会翻转。四个按钮安装在一个可以旋转的正方形的四个顶点上。

在任意一步，你都可以同时按下任意一个子集的按钮；但按完以后，对手都会把这个正方形旋转一下。

问：是否存在一种算法，保证无论初始状态如何、对手怎样旋转，你都能在某个固定步数之内把灯点亮？

分析

答案是：有。

两个按钮的简单版本

先看一个更简单的两按钮版本。若只有两个按钮，那么灯灭时本质上只有两类状态：\(00\)和\(01\)。这时用

双按 -> 单按 -> 双按

就能保证3步内点亮：

1. 先双按。如果原来是\(00\)，就直接到\(11\)；如果灯还没亮，就说明当前只能是\(01\)。
2. 再单按。这一步要么直接到\(11\)，要么把状态变成\(00\)。
3. 如果还没亮，最后再双按，就一定到\(11\)。

四个按钮的解法

四按钮题更难，是因为“灯灭”时不再只有两类状态，而是有更多种相对位置需要区分。

由于每一步之后对手都可以旋转正方形，所以具体哪个角上是哪一个按钮并不重要；真正重要的，只是当前有多少个开关闭合，以及它们的相对位置。

在“灯还没亮”的前提下，状态按旋转同构只分成5类：

1. 0闭合：4个开关全都断开。
2. 1闭合：恰有1个开关闭合。
3. 2邻：恰有2个相邻的开关闭合。
4. 2对：恰有2个对角的开关闭合。
5. 3闭合：恰有3个开关闭合。

可以用下面这个图例来记忆。这里1表示闭合，0表示断开；旋转后仍算同一类：

0闭合    1闭合    2邻      2对      3闭合
0 0      1 0      1 1      1 0      1 1
0 0      0 0      0 0      0 1      1 0

只用4种操作就够了：全按、对角、相邻、单按。做法不是追踪某个具体按钮，而是追踪“当前可能属于哪些状态类”，并把这个可能集合一步步缩小。

从一开始，灯没亮，所以可能状态集合是：

\[ \{0闭合,1闭合,2邻,2对,3闭合\}\]

如果中途灯亮，就已经成功；如果一直没亮，可以分成两段来看。

先看前7步：

全按 -> 对角 -> 全按 -> 相邻 -> 全按 -> 对角 -> 全按

下面这个“排除表”的意思是：做完该操作以后，如果灯还没亮，那么操作后的当前状态不可能是表中被排除的那一类。

更具体地说：如果原来真是2邻，那么执行一次相邻操作后，可能发生三种情况：

1. 直接到全闭合亮态；
2. 变成0闭合；
3. 变成2对。

所以，如果第4步之后灯还没亮，那么由原来的2邻出发，结果只可能是0闭合或2对，不一定是2对，但一定不可能还是2邻。

到这里为止，只剩下两种可能：1闭合或3闭合。

然后看最后8步：

单按 -> 全按 -> 对角 -> 全按 -> 相邻 -> 全按 -> 对角 -> 全按

这8步是在小集合{1闭合,3闭合}里继续压缩，直到只剩唯一的亮态：

最后到达全闭合亮态，灯必亮。

因此，确实存在一种算法，保证在至多15步之内一定把灯点亮。

数学本质

这道题表面上像一个“猜按钮”的脑筋急转弯，底层其实是一个很标准的有限状态空间+对抗信息不完全问题。

1. 先把真实状态写成一个4位01向量。

设4个开关的状态为

\[ x=(x_1,x_2,x_3,x_4)\in\{0,1\}^4\]

其中\(x_i=1\)表示第\(i\)个开关闭合，\(x_i=0\)表示断开。按下一组按钮，本质上就是把对应坐标翻转，也就是与一个01向量做按位异或：

\[ x\mapsto x\oplus a\]

这里\(a\in\{0,1\}^4\)表示这一步按了哪些按钮。

2. 真正重要的不是16个原始状态，而是它们在旋转下的等价类。

因为每一步之后对手都可以旋转正方形，所以你无法区分两个“只差一个旋转”的状态。也就是说，玩家真正面对的不是16个状态本身，而是它们在旋转群\(C_4\)作用下形成的轨道。

在灯灭的15个状态里，旋转以后只剩下5个本质不同的轨道，也就是文中的5类：

\[ 0000,\quad 1000,\quad 1100,\quad 1010,\quad 1110\]

它们分别对应：0闭合、1闭合、2邻、2对、3闭合。再加上唯一的亮态\(1111\)，整个问题就被压缩成了一个很小的有限系统。

3. 题目真正追踪的不是“真实状态”，而是“信息集”。

由于你每一步只能观察到“灯亮”或“灯不亮”，所以你通常不知道当前到底是哪一个具体轨道，只知道它属于某个可能集合。这个可能集合就叫信息集。

一开始灯没亮，所以初始信息集是

\[ K_0=\{0闭合,1闭合,2邻,2对,3闭合\}\]

每做一步操作，如果灯亮，就直接成功；如果灯还没亮，就把那些“本来会导致亮灯”的情况删掉，于是信息集缩小成一个新的集合。文中的两张表，做的正是这件事。

4. 所谓“算法存在”，本质上就是存在一条把信息集不断压缩的路径。

所以这题并不是在碰运气，而是在一个有限图上找一条必胜路径：

• 图的节点是各种可能的信息集；
• 图的边对应你选择的一种操作；
• 每次走边以后，如果仍不亮，就进入一个更小的信息集；
• 最终把信息集压到{0闭合}，再全按一次，就进入全闭合亮态。

换句话说，这道题的核心不是“猜中当前方向”，而是“无论对手怎样旋转，都要让剩余可能性越来越少”。

5. 为什么只需要考虑4种操作。

从形式上说，一步操作原本有\(2^4=16\)种，因为你可以按任意子集的按钮。但在旋转对称下，真正不同的操作类型只有少数几种：

1. 不按任何按钮；
2. 按1个按钮；
3. 按2个相邻按钮；
4. 按2个对角按钮；
5. 按3个按钮；
6. 按4个按钮。

其中“不按”显然没有帮助；“按3个按钮”和“按1个按钮”本质上只差一次全按，所以不需要单独作为新类型考虑。因此最后只保留4种关键操作：单按、相邻、对角、全按。

这就是这道题背后的数学结构：

二进制状态 + 旋转对称 + 信息集更新 + 有限步必胜策略

把这4件事看清楚以后，15步的构造就不再是神秘技巧，而是一个有限状态系统里的消元过程。