魔方吧·中文魔方俱乐部

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

各种囚犯问题(第1,2,4(1)已解出) [复制链接]

Rank: 7Rank: 7Rank: 7

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

中国纪录 八年元老

发表于 2010-11-29 15:49:27 |显示全部楼层
1.对100个囚徒,法官给每个囚徒指派一个1到100之间的编号,不同的囚犯编号可能会重复。每个囚徒知道别人的编号,但是不知道自己的。然后法官给每个囚徒一次机会猜测自己的编号。现在的提问是:如果发编号之前,囚犯可是商量一个对策,有什么策略能保证至少有一个囚徒能猜对自己的编号?
2.100个囚犯,每个人头顶上有一个黑帽子或者白帽子,至少有一个黑帽子,每个人可以看到其他人帽子的颜色却看不到自己的,监狱长先让大家看看别人头顶上戴的是什么帽子,然后关灯,如果有人认为自己戴的是黑帽子,就拍手,第一次关灯没有声音,第二次也没有,一直到第5次,才有声音响起,问有多少人带着黑帽子?
3.(1)有100个囚犯分别关在100间牢房里。牢房外有一个空荡荡的房间,房间里有一个由开关控制的灯泡。初始时,灯是关着的。看守每次随便选择一名囚犯进入房间,但保证每个囚犯都会被选中无穷多次。如果在某一时刻,有囚犯成功断定出所有人都进过这个房间了,所有囚犯都能释放。游戏开始前,所有囚犯可以聚在一起商量对策,但在此之后它们唯一可用来交流的工具就只有那个灯泡。他们应该设计一个怎样的协议呢?
(2)大家都知道房间里的灯泡一开始是不亮的。如果灯泡的初始状态并不确定,问题有解吗?
(3)在以上协议中,只有一个人能知道所有人都来过房间。是否存在一个协议,使得最终可以产生两个人,他们都知道所有人都进过房间?如果存在这样的协议,给出一个来;如果不存在,证明之。为了方便思考,你可以暂时假设初始时房间的灯泡不亮。
(4)还是100个囚犯,还是一个空房间,还是要求所有囚犯事先构造一个协议,能保证有人可以断定出所有人都来过房间。不过,这次不同的是,房间里有两个灯泡,分别由两个开关来控制(不妨假设初始时他们都是不亮的)。大家估计要说了,一个灯泡都能解决的事儿,用两个灯泡还不容易?嘿嘿,这次有一个附加的要求:所有人都必须遵循同一套策略。
4.(1)100个囚犯从前往后坐成一列。坐在最后面的那个囚犯能够看到其余99个囚犯,坐在最前面的那个囚犯啥也看不见。看守给每个囚犯戴上一顶黑色的或者白色的帽子。然后,看守会从后往前依次叫这些囚犯猜测自己头顶上的帽子的颜色。如果哪个囚犯猜对了,他就自由了。坐在前面的每一个囚犯都可以听到后面的囚犯的猜测。如果这100个囚犯事先可以商量好一种策略,那么最理想的策略是什么?
(2)无穷个囚犯面向数轴的正方向依次就座,第i个囚犯坐在数轴上坐标为i的地方,他可以看见所有坐标大于i的囚犯头顶上的帽子。看守给每个囚犯戴上黑色或白色的帽子,然后依次叫每个囚犯猜测自己头上的帽子颜色,猜对了的予以释放。另外一点和原来不同的是,囚犯们不能听到其他人的猜测。另外注意到,由于每个人前面都有无穷多个人,因此囚犯们无法通过数他前面的人数来判断出自己的位置,于是我们不得不加上一句:每个人都知道他后面有多少人(即他是第几个被问的)。同样地,事先所有囚犯可以商量出一个策略,它可以保证除了有限个囚犯之外,其他囚犯全部释放!你能想出这个策略吗?
5.典狱长要和100个囚犯玩这么一个游戏。典狱长给每个囚犯发两个手套,一个黑色的,一个白色的。之后,每个囚犯的额头上都会写上一个实数,所有这100个实数互不相同。每个囚犯都能看到其他99个囚犯前额上所写的数,但不能看到自己的数。接下来,每个囚犯必须独立地决定把哪个手套戴在哪只手上。等到所有囚犯都戴好了手套,典狱长会把他们按照前额上所写的数从小到大地排好,并要求他们手牵着手站成一横排。如果每两只握在一起的手都戴着相同颜色的手套,那么所有100个囚犯都可以被释放。在游戏开始前,他们可以聚在一起,商量一个对策。游戏开始后,囚犯与囚犯之间不允许有任何交流。囚犯们能够保证全部释放吗?
19events = 644days
PB (2 3 4 5)B = 1200seconds
北大魔方爱好者QQ群74893945
mf8最少步讨论群:RP与公式的绝佳配合QQ群5652935

Rank: 7Rank: 7Rank: 7

积分
3503
帖子
2290
精华
1
UID
18891
性别
保密

六年元老

发表于 2010-11-29 15:57:37 |显示全部楼层
看了第一个,先说说1、不清楚怎么猜测的。囚徒是否可以知道别人猜测的号码是多少,如果可以,大家都猜测张三的号码。张三自然就知道自己的号码了。
拿起你的魔方,我们就是朋友了!
你准备好了吗?

使用道具 举报

Rank: 4

积分
1041
帖子
942
精华
0
UID
1263127
性别

两年元老

发表于 2010-11-29 15:58:34 |显示全部楼层
典狱长不好当啊!要何等的智商啊!

使用道具 举报

Rank: 4

积分
1479
帖子
1304
精华
0
UID
1236564
性别
保密

四年元老

发表于 2010-11-29 16:08:27 |显示全部楼层

回复 3# 的帖子

囚犯也不好当啊 除了受刑 还要接受智力测试
放假 过年
新品特价
http://shop59035917.taobao.com/

使用道具 举报

Rank: 3Rank: 3

积分
600
帖子
524
精华
0
UID
94294
性别

四年元老

发表于 2010-11-29 16:34:41 |显示全部楼层
第一个问题我想是:“如果看到有重复号的话,举手示意一下”这样如果没有举手的,大家就都知道没有重复的,就知道自己的编号了,如果有举手的,就说明有重复的,那样没举手两个人就号码一样,所以他们就知道编号了

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
3503
帖子
2290
精华
1
UID
18891
性别
保密

六年元老

发表于 2010-11-29 16:41:10 |显示全部楼层
原帖由 godtm 于 2010-11-29 16:34 发表
第一个问题我想是:“如果看到有重复号的话,举手示意一下”这样如果没有举手的,大家就都知道没有重复的,就知道自己的编号了,如果有举手的,就说明有重复的,那样没举手两个人就号码一样,所以他们就知道编号了

你的解法默认了一个条件,就是大家坐在一起猜,或者说猜测者可以看到别人的动作。
那么完全可以这样:开始商量好,大家都用手势做出张三的号码。
轮到张三猜测的时候,他看别人的手势就可以了。
拿起你的魔方,我们就是朋友了!
你准备好了吗?

使用道具 举报

银魔

十字手

Rank: 7Rank: 7Rank: 7

积分
2956
帖子
2167
精华
1
UID
25131
性别

中国纪录 六年元老

发表于 2010-11-29 16:46:19 |显示全部楼层
占位思考……
一蓑烟雨任平生
我已厌倦看穿虚伪,请隐藏好你内心的丑恶念头与每一丝邪念。
天主,你曾使圣十字若望忘我牺牲,热爱十字圣架;求你使我们现世追随他的芳表,将来也能永远瞻仰你的光荣。因你的圣子、我们的主耶稣基

使用道具 举报

Rank: 3Rank: 3

积分
600
帖子
524
精华
0
UID
94294
性别

四年元老

发表于 2010-11-29 16:49:31 |显示全部楼层
原帖由 rubik-fan 于 2010-11-29 16:41 发表

你的解法默认了一个条件,就是大家坐在一起猜,或者说猜测者可以看到别人的动作。
那么完全可以这样:开始商量好,大家都用手势做出张三的号码。
轮到张三猜测的时候,他看别人的手势就可以了。
那是我想的简单了。
如果不能做手势的话,那只有第一个人报出别人头上的数字(当然他会报重复最多的人的数字),然后所有人都重复报这个数字,总有能“猜”对了的
如果第一个人看到没有重复的数字,就知道自己的数字了,那他就报自己的数字,这样大家就都知道没有重复的了,那所有人就都“猜”对了。

另外,第二题,第几次关灯就有几个人符合要求,所以是5
4(1)想到了,是不是第一个猜的人猜人数多的帽子颜色,然后其他人都猜这一颜色,这样可以让大多数人猜对?

[ 本帖最后由 godtm 于 2010-11-29 16:55 编辑 ]

使用道具 举报

Rank: 2

积分
596
帖子
549
精华
0
UID
1251450
性别
保密
发表于 2010-11-29 18:07:34 |显示全部楼层
原帖由 godtm 于 2010-11-29 16:49 发表
那是我想的简单了。
如果不能做手势的话,那只有第一个人报出别人头上的数字(当然他会报重复最多的人的数字),然后所有人都重复报这个数字,总有能“猜”对了的
如果第一个人看到没有重复的数字,就知道自己的数 ...

猜的过程不是所有人一起进行的,猜的过程是和典狱长一起进行的
除了一开始的交流之外,所有人就不能再获取信息了

使用道具 举报

Rank: 2

积分
221
帖子
211
精华
0
UID
1270974
性别
发表于 2010-11-29 18:13:50 |显示全部楼层
有什么策略能保证至少有一个囚徒能猜对自己的编号?  这个简单,大家都猜一个号   肯定至少有一个猜对的

使用道具 举报

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

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

GMT+8, 2019-6-17 13:38

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部