[组合] NMO试题组合部分

hbghlyj

29.给定正整数n,图G中不含长度>2n的圈,证明:G中的点可以n-染色,使得G中不含同色的圈
30.有9名囚犯被关在各自的房间内,由典狱长看管,这名典狱长在某天在监狱走廊上放置了一些灯笼,并发布了一条奇怪的命命:从今晚起,他会随机抽一名犯人在走廊上放风.被抽到的犯人必须执行,且不会有他人顶替.随后又说明这是决定他们生死的一场游戏,并给出游戏内容与对应规则.这些囚犯在游戏开始前有一定讨论时间,并且游戏期间不可交流.
(1)走廊上只放置1盏灯,在之后的任意一天,哪位犯人认为自己放完风后,所有人都已经放过至少一次风便可向典狱长汇报,如果是,所有人即可出狱,如果不是,则处死所有人.
问:他们能否出狱?(只需回答是或否)
(2)在游戏(1)的情况下,如果他们能成功出狱,那么请指出在使用最优策略下的刑期的天数的期望,并说明最优策略;若不能,请指出最少需要几盏灯笼,并指出使用该数量下的灯笼的最优策略.
(3)典狱长要求在第九个放风的人一出来便去报告,请指出至少要几盏灯笼,并给出证明.
6.有一个n边形的转台,在每个顶点处有一个凹坑,内放一玻璃杯,玻璃杯有正反两种状态,但因被布蒙起,故无法识别状态.以此为道具,设计一个游戏.玩家每次可以选择k个玻璃杯,用手感受状态,并决定是否翻转.每次玩家操作结束后,转台会旋转,改变凹坑方向,使凹坑的相对位置改变,但绝对位置(可能)改变(注,即整个转台旋转前后保持全等)使操作时改变的玻璃杯对应凹坑位置无法确定.求最小的k使得游戏在有限步内结束.