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

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

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

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

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

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


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

    下面我们用数学归纳法来说明,当 n = 2k 时,国王都有必胜策略。为此,我们只需要说明,如果对于某个 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 写成 2k · m ,其中 m 是一个奇数。现在,我们从某盏灯出发,选出每第 2k 盏灯,从而选出间隔均等的 m 盏灯。国王下达指令后,我们也只关心这 m 盏灯所对应的人是否被叫到,并限定圆桌只能旋转 2k 的倍数格。这样,我们便可以完全把其他灯都无视掉,对这 m 盏灯套用灯数为奇数时的做法,从而让这 m 盏灯始终不能全亮。这就足以让会议无限延期了。

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

29 条评论

回复给 hafiuy 取消回复

32  +    =  37