魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
查看: 607|回复: 3

旋转桌子避免灯泡全亮 from matrix67 [复制链接]

Rank: 7Rank: 7Rank: 7

积分
2520
帖子
3072
精华
7
UID
62890
性别

中国纪录 八年元老

发表于 2011-10-5 19:33:53 |显示全部楼层
某个国王手下有 n 个大臣。国王定期主持国家会议,届时 n 个大臣将会间隔均匀地坐在圆桌上。每个座位前都有一盏照明灯,只有所有的灯都亮了,会议才能开始进行。如果有些灯没亮,国王会下达指令,让指定位置上的大臣按下座位前的灯的开关,把没亮的灯都打开。例如,当 n = 100 时,圆桌上会坐着 100 个大臣。不妨将座位从 1 到 n 顺序编号,假设其中编号为 3 、 28 、 97 的座位前没有亮灯。于是,国王下令这三个位置上的大臣按下各自面前的开关,把这三盏灯打开,这样才能开始会议议程。
    在这 n 个大臣中,有一个奸臣。这次会议的议题恰好就是商讨对这个奸臣的惩治办法。奸臣知道自己难逃一劫,但他希望能够无限制地拖延会议。他可以在所有大臣就座前精心设置各个照明灯的初始状态,并在国王每次下达指令之后(但在大臣执行命令之前)把圆桌旋转到一个合适的位置,让大臣们按下错误的开关。
    对于哪些 n ,奸臣可以始终保证灯不会全亮,从而无限制地拖延会议?对于哪些 n ,国王可以根据局势巧妙地构造指令,使得有限轮指令之后所有灯必然全亮?
    在会议结束前,奸臣仍然是 n 个大臣中的一员。国王每次只能下达形如“座位编号为 a1, a2, a3, … 的大臣改变各自面前的灯的状态”的指令。奸臣可以任意旋转圆桌,改变灯与大臣的对应关系。当然,他也可以选择不旋转圆桌。即使桌子被旋转过,所有大臣也必须严格遵守国王的指令。
19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群:RP与公式的绝佳配合QQ群5652935

Rank: 4

积分
1360
帖子
1033
精华
11
UID
96089
WCA ID
2010JIMO01
兴趣爱好
破解

亚洲纪录(AsR) 六年元老

发表于 2011-10-5 20:17:49 |显示全部楼层
猜测:N是质数奸臣胜利,是合数国王胜利???
以前看过一个类似解法的题。4盏灯的时候貌似是国王7步必胜

使用道具 举报

Rank: 4

积分
1222
帖子
661
精华
2
UID
1256325
性别

四年元老

发表于 2011-10-5 20:22:52 |显示全部楼层
冗长的表达方法是我不想研究的重大理由
精明的国王是这样表达的:你们看哈灯亮完没有,没亮的都开亮,然后开会
毕竟一堆大臣里面只有一个奸臣是这个国家的福气啊

使用道具 举报

透魔

是术术是?

Rank: 6Rank: 6

积分
5181
帖子
4706
精华
0
UID
1299116
性别
居住地
丹麦
兴趣爱好
其它

六年元老

发表于 2011-10-5 22:55:50 |显示全部楼层
我也占个楼,然后想想解答~~~
欲壑难填
一定要善良
宽于待人、严于律己
把2014活到人生的顶峰
拧魔如逆水行舟,不进则退

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2020-12-5 23:14

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部