趣题：旋转桌子避免灯泡全亮

    网友 @ipondering 分享了一个非常精彩的数学趣题集，里面有很多我之前从没见过的趣题，其中有些问题的题目和解答都相当漂亮。近段时间里，我打算从中选一些最精彩的题目来讲讲。今天的题目是该趣题集中的第二题，原题背景涉及到 King Arthur 和 Merlin 的故事，我就舍去简化了。

    某个国王手下有 n 个大臣。国王定期主持国家会议，届时 n 个大臣将会间隔均匀地坐在圆桌上。每个座位前都有一盏照明灯，只有所有的灯都亮了，会议才能开始进行。如果有些灯没亮，国王会下达指令，让指定位置上的大臣按下座位前的灯的开关，把没亮的灯都打开。例如，当 n = 100 时，圆桌上会坐着 100 个大臣。不妨将座位从 1 到 n 顺序编号，假设其中编号为 3 、 28 、 97 的座位前没有亮灯。于是，国王下令这三个位置上的大臣按下各自面前的开关，把这三盏灯打开，这样才能开始会议议程。

    在这 n 个大臣中，有一个奸臣。这次会议的议题恰好就是商讨对这个奸臣的惩治办法。奸臣知道自己难逃一劫，但他希望能够无限制地拖延会议。他可以在所有大臣就座前精心设置各个照明灯的初始状态，并在国王每次下达指令之后（但在大臣执行命令之前）把圆桌旋转到一个合适的位置，让大臣们按下错误的开关。

    对于哪些 n ，奸臣可以始终保证灯不会全亮，从而无限制地拖延会议？对于哪些 n ，国王可以根据局势巧妙地构造指令，使得有限轮指令之后所有灯必然全亮？

    在会议结束前，奸臣仍然是 n 个大臣中的一员。国王每次只能下达形如“座位编号为 a₁, a₂, a₃, … 的大臣改变各自面前的灯的状态”的指令。奸臣可以任意旋转圆桌，改变灯与大臣的对应关系。当然，他也可以选择不旋转圆桌。即使桌子被旋转过，所有大臣也必须严格遵守国王的指令。

 
    我们来看两个例子吧。首先，当 n = 1 时，国王显然是必胜的。当 n = 2 时，国王也是必胜的。注意到，如果两灯状态相同，国王便立即获胜了。如果初始时两灯状态不同，国王可以随便叫某个人按下开关。不管奸臣是否旋转圆桌，两灯状态都会变得相同，国王便可在第二轮获胜。

    下面我们用数学归纳法来说明，当 n = 2^k 时，国王都有必胜策略。为此，我们只需要说明，如果对于某个 n ，国王有必胜策略，那么对于 2n 的情况，国王也有必胜策略。首先，把每两个关于圆桌中心对称的灯视为一组，这样就把 2n 个灯分成了 n 组。把这 n 组灯看作是 n 个“超级灯”。如果一组灯里的两个灯泡状态相同，我们就认为这个超级灯发亮；如果这组灯里的两个灯泡状态不同，就认为这个超级灯不亮。接下来，国王只对编号为 1, 2, 3, …, n 范围内的座位下达命令，那么不管奸臣怎么旋转圆桌，他都最多只能改变每组灯里的其中一个灯泡。事实上，我们完全可以把现在的情形等价地想像成这样：圆桌旁有 2n 个座位， n 个大臣坐满圆桌的其中半边；桌上则有 n 个超级灯，旋转圆桌半周正好让这 n 个超级灯重新回到初始位置。由归纳假设，对于 n 个灯泡的情形国王可以必胜，因此现在，国王可以套用这个算法，让每一个超级灯都发亮。换句话说，国王能够让位于对称位置上的每一组灯都处于相同的状态。

    接下来，国王把每两个处于对称位置的座位也编为一组，换句话说就是把 2n 个座位分成了 (1, n+1), (2, n+2), …, (n - 1, 2n - 1), (n, 2n) 共 n 组。此后，国王总是成组地下达指令，叫某个人按下开关，必须要叫和他同组的另一个人也按下开关。这下，不管奸臣怎么旋转圆桌，每组灯里的灯泡状态要么同时改变，要么都不变，于是每组灯里两个灯泡的状态都继续保持相同。重新解释超级灯的状态：如果这组灯的两个灯泡都亮，就认为这个超级灯是亮的；如果这组灯的两个灯泡都不亮，则认为这个超级灯不亮。容易看出，这下又成了这样的情况： n 组人操作 n 个超级灯，桌子每转半周就会回到原来的位置。因此，国王再次套用 n 个灯时的算法，便能让所有超级灯都发亮。这样，所有 2n 个灯泡也都亮了。

 
    下面我们说明，当 n 不是 2 的幂时，奸臣可以无限拖延会议。让我们先来看一个简单的情况。当 n 是奇数时，只要初始时灯泡不全亮也不全灭，奸臣都能必胜。注意到，如果灯泡既没全亮又没全灭，那么我们一定能找到相邻的两盏灯，他们是一亮一灭的。奸臣可以保证今后这两盏灯始终一亮一灭。如果国王对所有人都下指令，奸臣大可不必担心，这两盏灯显然仍然一亮一灭。如果国王只对一部分人下指令，那么由于 n 是奇数，因而即使国王故意间隔着选人，也将不可避免地出现两个相邻的人，他们都被叫到了或者都没被叫到。此时，奸臣旋转桌子，让那两盏灯对齐这两个人，从而保持这两盏灯仍然一亮一灭。

    事实上，只要 n 不是 2 的幂，我们都有类似的方法。把 n 写成 2^k · m ，其中 m 是一个奇数。现在，我们从某盏灯出发，选出每第 2^k 盏灯，从而选出间隔均等的 m 盏灯。国王下达指令后，我们也只关心这 m 盏灯所对应的人是否被叫到，并限定圆桌只能旋转 2^k 的倍数格。这样，我们便可以完全把其他灯都无视掉，对这 m 盏灯套用灯数为奇数时的做法，从而让这 m 盏灯始终不能全亮。这就足以让会议无限延期了。

 
题目来源：http://www.cs.cmu.edu/puzzle/puzzle2.html