魔方吧·中文魔方俱乐部

标题: 旋转桌子避免灯泡全亮 from matrix67 [打印本页]

作者: superacid 时间: 2011-10-5 19:33:53 标题: 旋转桌子避免灯泡全亮 from matrix67

某个国王手下有 n 个大臣。国王定期主持国家会议，届时 n 个大臣将会间隔均匀地坐在圆桌上。每个座位前都有一盏照明灯，只有所有的灯都亮了，会议才能开始进行。如果有些灯没亮，国王会下达指令，让指定位置上的大臣按下座位前的灯的开关，把没亮的灯都打开。例如，当 n = 100 时，圆桌上会坐着 100 个大臣。不妨将座位从 1 到 n 顺序编号，假设其中编号为 3 、 28 、 97 的座位前没有亮灯。于是，国王下令这三个位置上的大臣按下各自面前的开关，把这三盏灯打开，这样才能开始会议议程。
在这 n 个大臣中，有一个奸臣。这次会议的议题恰好就是商讨对这个奸臣的惩治办法。奸臣知道自己难逃一劫，但他希望能够无限制地拖延会议。他可以在所有大臣就座前精心设置各个照明灯的初始状态，并在国王每次下达指令之后（但在大臣执行命令之前）把圆桌旋转到一个合适的位置，让大臣们按下错误的开关。
对于哪些 n ，奸臣可以始终保证灯不会全亮，从而无限制地拖延会议？对于哪些 n ，国王可以根据局势巧妙地构造指令，使得有限轮指令之后所有灯必然全亮？
在会议结束前，奸臣仍然是 n 个大臣中的一员。国王每次只能下达形如“座位编号为 a1, a2, a3, … 的大臣改变各自面前的灯的状态”的指令。奸臣可以任意旋转圆桌，改变灯与大臣的对应关系。当然，他也可以选择不旋转圆桌。即使桌子被旋转过，所有大臣也必须严格遵守国王的指令。

作者: jimofc 时间: 2011-10-5 20:17:49

猜测：N是质数奸臣胜利，是合数国王胜利？？？
以前看过一个类似解法的题。4盏灯的时候貌似是国王7步必胜

作者: 冷帝 时间: 2011-10-5 20:22:52

冗长的表达方法是我不想研究的重大理由
精明的国王是这样表达的：你们看哈灯亮完没有，没亮的都开亮，然后开会
毕竟一堆大臣里面只有一个奸臣是这个国家的福气啊

作者: 潜水艇 时间: 2011-10-5 22:55:50

我也占个楼，然后想想解答~~~

欢迎光临魔方吧·中文魔方俱乐部 (http://www.mf8-china.com/)