魔方吧·中文魔方俱乐部

标题: 各种囚犯问题(第1,2,4(1)已解出) [打印本页]

作者: superacid 时间: 2010-11-29 15:49:27 标题: 各种囚犯问题(第1,2,4(1)已解出)

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个囚犯都可以被释放。在游戏开始前，他们可以聚在一起，商量一个对策。游戏开始后，囚犯与囚犯之间不允许有任何交流。囚犯们能够保证全部释放吗？

作者: rubik-fan 时间: 2010-11-29 15:57:37

看了第一个，先说说1、不清楚怎么猜测的。囚徒是否可以知道别人猜测的号码是多少，如果可以，大家都猜测张三的号码。张三自然就知道自己的号码了。

作者: liuliuliu789123 时间: 2010-11-29 15:58:34

典狱长不好当啊！要何等的智商啊！

作者: 勇闯魔界 时间: 2010-11-29 16:08:27 标题: 回复 3# 的帖子

囚犯也不好当啊除了受刑还要接受智力测试

作者: godtm 时间: 2010-11-29 16:34:41

第一个问题我想是：“如果看到有重复号的话，举手示意一下”这样如果没有举手的，大家就都知道没有重复的，就知道自己的编号了，如果有举手的，就说明有重复的，那样没举手两个人就号码一样，所以他们就知道编号了

作者: rubik-fan 时间: 2010-11-29 16:41:10

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

你的解法默认了一个条件，就是大家坐在一起猜，或者说猜测者可以看到别人的动作。
那么完全可以这样：开始商量好，大家都用手势做出张三的号码。
轮到张三猜测的时候，他看别人的手势就可以了。

作者: rcsgqty 时间: 2010-11-29 16:46:19

占位思考……

作者: godtm 时间: 2010-11-29 16:49:31

原帖由 rubik-fan 于 2010-11-29 16:41 发表

你的解法默认了一个条件，就是大家坐在一起猜，或者说猜测者可以看到别人的动作。
那么完全可以这样：开始商量好，大家都用手势做出张三的号码。
轮到张三猜测的时候，他看别人的手势就可以了。

那是我想的简单了。
如果不能做手势的话，那只有第一个人报出别人头上的数字（当然他会报重复最多的人的数字），然后所有人都重复报这个数字，总有能“猜”对了的
如果第一个人看到没有重复的数字，就知道自己的数字了，那他就报自己的数字，这样大家就都知道没有重复的了，那所有人就都“猜”对了。

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

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

作者: 夜半猫叫 时间: 2010-11-29 18:07:34

原帖由 godtm 于 2010-11-29 16:49 发表
那是我想的简单了。
如果不能做手势的话，那只有第一个人报出别人头上的数字（当然他会报重复最多的人的数字），然后所有人都重复报这个数字，总有能“猜”对了的
如果第一个人看到没有重复的数字，就知道自己的数 ...

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

作者: 味道 时间: 2010-11-29 18:13:50

有什么策略能保证至少有一个囚徒能猜对自己的编号？这个简单，大家都猜一个号肯定至少有一个猜对的

作者: kattokid 时间: 2010-11-29 18:15:02

如果还能听到别人猜的话那就相当简单了，第一个人说一个某人的编号，大家都猜这个数不就行了…感觉可以这样，猜测的顺序如果可以由囚犯们自己选择，那第一题我想应该就可以解了，如果是固定的顺序…还没想出结果…

[ 本帖最后由 kattokid 于 2010-11-29 18:18 编辑 ]

作者: phileas 时间: 2010-11-29 20:17:13

第1题: 假设第i号囚徒身上的编号是bi，他猜编号ai：其中1<=ai<=n，且"ai" 与 "-bj的和(j 不等于 i) + i" 模n同余。
考察 ai - bi = i - 所有bj的和，是n个连续整数，其中必有一个被n整除，注意到 -(n-1) <= ai - bi <= n - 1，这个被n整除的必然是0。
于是至少有一个囚徒猜对。

作者: phileas 时间: 2010-11-29 20:21:19

第2题：
如果看到都是白帽子，那么自己必然是黑帽子。于是第1天没人说知道了 => 至少2顶黑帽子
由此可以推出：第n天没人说知道了 => 至少n+1顶黑帽子。
并且：第n天有人说知道了，恰好n顶黑帽子(看到n-1顶，以及自己头上1顶)。

作者: phileas 时间: 2010-11-29 20:30:09

第4题1：
第一个猜的人，如果看到前面的黑帽子一共偶数顶，就说白色；如果是奇数顶，就说黑色。
这样之后猜的人，可以根据前面帽子的奇偶性和后面的人的回答，全部猜对。

作者: superacid 时间: 2010-11-29 21:22:15

顶到n楼之后发解答

作者: tm__xk 时间: 2010-11-30 01:47:14

这个必须顶........

作者: godtm 时间: 2010-11-30 07:43:21

原帖由 phileas 于 2010-11-29 20:30 发表
第4题1：
第一个猜的人，如果看到前面的黑帽子一共偶数顶，就说白色；如果是奇数顶，就说黑色。
这样之后猜的人，可以根据前面帽子的奇偶性和后面的人的回答，全部猜对。

原来是这样啊！看来是我想简单了！这样果然比我想的要好！

作者: kattokid 时间: 2010-11-30 08:42:35

第二题感觉是5顶黑帽子…
第三题不知可否用数人头的方法，第一次进房间的亮灯一次，再次进入房间就不亮灯了，如此亮过100次，即可知100人都进过房间
如果我第一问做对，第二问应该可以根据奇偶判定。

作者: 骰迷 时间: 2010-12-11 23:09:29

１２樓的答案看不明白，求詳解
４（２）思考：坐在i座標的囚犯，無論黑或白，所獲得的資訊都是一樣的（少），能靠甚麼判斷呢？

[ 本帖最后由骰迷于 2010-12-11 23:21 编辑 ]

作者: 骰迷 时间: 2010-12-13 20:53:22

3(1)一人數人頭，其他人亮燈一次，數人頭的數到99便可以判斷全部人都進過來了。
3(2)一人數人頭，其他人亮燈兩次，數人頭的數到198便可以判斷全部人都進過來了。

作者: 骰迷 时间: 2010-12-13 21:09:36

3(3)前半部跟3(1)一樣，先由一個人知道了全部人已經來過。之後他每一次進房都把燈的狀態轉變，其他人從一開始一直數燈轉變的次數（包括自己轉的），正常來說當燈轉變198次後，所有人都已經進過了房間。所以當他們其中一人數到198時，他就知道所有人都已經進過了房間，這樣就有兩人了。
這方法的缺點１：需時太久，２：若獄卒都是挑時間放囚犯進去的，所有囚犯每次進去都看到燈亮著，便失敗了。
這其實是一個作弊的方法。

作者: 喝着牛奶数星星 时间: 2010-12-13 21:14:16

这可真是费脑子

作者: 业余魔术师 时间: 2010-12-13 21:18:19

就看了第一个,后面的大概看了看,戴帽子的那个知道答案,灯泡的以前也看过.
我想说说第1个.
如果一个囚徒知道其余99个囚徒的号码,又怎么会不知道自己的号码呢???????

作者: 骰迷 时间: 2010-12-13 22:04:30 标题: 回复 23# 的帖子

號碼有重複的，請看題

作者: superacid 时间: 2011-2-13 17:01:29

没事顶一下吧，题目还是挺有意思的

作者: tm__xk 时间: 2011-7-2 03:17:43

都木有人了..放个第5题的标准解..
事先编号.
每个人的选择为其他人逆序数与自身编号之和mod2.
不多解释了.

作者: soholi 时间: 2012-12-27 10:53:59

顶起，思考中。。。

作者: liang54858542 时间: 2013-8-8 19:52:05

能不能解决了？？

作者: mb9922 时间: 2013-12-27 22:35:13

关于灯泡的，我觉得可以让每一个第一次出来的囚徒闪一次灯，第一个一下，第二个两下，重复的不闪或者闪原来已经闪过的次数，这样，就会在某一时刻1至100每个数都闪过，不过灯质量要好才行…………

作者: 5772156 时间: 2014-12-13 15:32:15

哎呀花了很大力气终于做出第五题了，心里很高兴。特地注册一个号给大家讲讲。

首先每个人看到的信息，本质上就是排成一行的大小序列

每个人要是可以猜出自己对应的实数的大小所在位置的奇偶性，奇的和偶的戴手套顺序不同，问题就解决了

可是呢，每个人都看不到自己的实数，也就不知道自己所在的位置

我们计划创造一个规则，通过看到别人带的实数猜到自己的实数。你可以说，不可能呀。我们的目标是，让所有人或者都猜对，或者都猜错，这样问题也能解决。

如何保证或者都猜对，或者都猜错呢？实际上，只需要保证任何两个编号相邻的人，他们猜的奇偶性不同，这样就可以啦。

那么我们很容易联想到置换的奇偶性。每个人都能看到一个置换，那就是把他看到的最小的实数记作1，最大的记作99，从自己顺时针的下一位开始顺时针走得到的排列。

两个对应实数相邻的人，他们看到对方的实数在其他所有人中的位置也是相同的。这样，两个对应实数相邻的人看到的置换之间，是有对应规律联系着的。

稍加研究，就能发现规律是这样：执行若干次长为99的轮换，再执行若干次对换，对换执行次数的奇偶性取决于他们之间夹着奇数个人还是偶数个人，也就是他们的距离是偶数还是奇数。
那么，如果每个人直接猜置换的奇偶性的话，他们两个在距离为偶数时所猜不同，在距离为奇数时所猜相同。
我们进行一个微调：提前选定一个人，在游戏进行时，把所有人染成黑白两色（当然是在想象中），使得被选定的人被染成黑色。被染成黑色的人，反转对自己奇偶性的猜测。

这样，问题就解决了~

作者: 百色面 时间: 2015-6-22 16:58:22

rubik-fan 发表于 2010-11-29 15:57
看了第一个，先说说1、不清楚怎么猜测的。囚徒是否可以知道别人猜测的号码是多少，如果可以，大家都猜测张三 ...

是的，为什么要这样多此一举呢

作者: 大大大魔方 时间: 2016-2-2 16:03:03

都不会字节字节

作者: 大大大魔方 时间: 2016-2-2 16:07:14

都好难啊，智商低确实不会

作者: fgmN 时间: 2016-4-25 19:15:52

5很容易挑其中两个数学好的人来排序就好了

作者: zhangrang 时间: 2017-1-19 11:54:28

我没看懂。噢，是看不懂。

作者: SnowMiku 时间: 2017-5-18 18:40:35

3(1)明白了。一个人负责数，灯亮了就关掉，其他人看到灯灭就打开，亮的或者开过就走。数的人看到第99次亮就说

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