SexInSex! Board - Powered by Discuz! Board

标题: [案发现场] 自救——补正【答案】 [打印本页]

作者: freeabc 时间: 2012-5-16 18:57 标题: 自救——补正【答案】

修正版

关在同牢房的十个犯人在前一天得到消息，他们将在第二天被处死。但为彰显天有好生之德的仁慈，会在最后再给他们一次生还的机会，若仍不能幸免则只能怪天意了。

机会就是：第二天会给每个人戴上一顶帽子，每个帽子上有个范围1-10的数字，不同帽子上的数字有可能相同。犯人看不到自己帽子上的数字，但可以看到其他所有人帽子上的数字，可以据此猜测自己帽子上的数字。

届时犯人彼此将被完全隔绝，除了能知道其他人头上帽子的数字外一无所知，彼此间无法以任何方式——包括动作表情声音眼神气味电磁场超能力等等——进行接触交流及任何信息的传递交换。每个犯人将在彼此隔绝状态下作出回答。

生还条件听上去很厚道，只要全部犯人中有一位猜对了自己帽子上的数字，则全部犯人都将给予赦免。请问他们有没有方法确保被赦免？生还的机会有多大？
————————————————————
答案：有。这其实是一个关于模运算的一个问题。

所有人的回答合在一起就可以是相关的。比如所有人的一个相关点就是所有十个数字的和是相同的一个值。
那么这个值对10取模，有0-9十种情况。
对于其中任何一个犯人，其他数字的和设为a，是已知的。自己的数字设为x。
那么令 (a+x) mod 10=0-9，会分别对应x取10，1，2，…，9十种情况。
所以每个犯人分别分配一个除以10的余数的取值，其中必有一个是正确的，据此确定的自己的数字也是正确和唯一的。

正确答案：11楼迅雷还真雷
————
根据前几楼的回复，对题目稍作补充，对“隔离”概念的理解进行了澄清。

[ 本帖最后由 freeabc 于 2012-5-19 19:51 编辑 ]

作者: sida1126 时间: 2012-5-16 21:14

如果至少有一个犯人猜对自己帽子上的数字，则全体犯人会得到一次赦免的机会。

看一下自己帽子上的数字不久知道了吗。

作者: kylin6lood 时间: 2012-5-16 21:23

从题目来看不能接触和交流是在戴上帽子后，在行刑前一天所有犯人还是在一起，那么实现约定好第一个回答的人大声说出他看到的其中一个数字，并且所有人都说这个数字即可，所谓不能交流不能接触并不代表不能互相听到吧，否则互相看清其他人的帽子标号就没有意义了

作者: zhoulei382 时间: 2012-5-16 21:39

第一个回答问题的犯人把自己把自己看到的数字说出来。然后其他犯人都说这个数字就可以了。这样总一个人能猜对。这样就能获得敕免的。

作者: microseee 时间: 2012-5-16 21:45

可以的假设大家围坐在一圈也许可以用眼神示意数字的大小和相同

作者: tigerzsu 时间: 2012-5-16 21:54

第一个犯人把自己看到的其他人头上的其中一个数字报出来。第二到第十个听到这个数字后都报这个数字。这样至少有一个人中。

作者: wjxxx11111 时间: 2012-5-16 21:59

不同帽子上的数字有可能相同。每个犯人将在隔离状态下单独秘密作出回答。如果其中有犯人刚好能猜对自己帽子上的数字，则全体犯人会得到一次赦免的机会。
猜自己帽子上的数字是看到的相同的数字，就有可能得到赦免的机会。且机会很大。

作者: gzadsl1234 时间: 2012-5-17 04:40

每个人将自己看到的帽子点数求平均值，并报上自己见到与之最接近的点数。
至于理由还没想好，凭感觉吧

[ 本帖最后由 gzadsl1234 于 2012-5-17 04:49 编辑 ]

作者: 老实的人 时间: 2012-5-17 08:02

很简单，每个人都说自己帽子上的数字上是1（或者是1~10之间任意一个数字）.总有一个人能猜对的。
有点风险，但是生存的几率非常大。

作者: Doreamon 时间: 2012-5-17 09:58

如果在回答的时候是彼此隔绝的，但是可以知道其他犯人到底有没有猜中他们自己帽子上的数据、以及其他犯人猜的数据是多少的话，那他们是可以存活的
方法如下：第一个犯人如果看到其他人帽子上的数字没有重复的话，那他就回答1-10中他没有看见的那个数字；如果看到其他人帽子上的数字有重复的话，那他就猜自己的帽子上也是那个重复的数字；
第二个犯人同理，看到其他人帽子数字不重复，回答没看见的数字；如果看到其他人帽子上有重复的数字，那他也猜那个重复的数字；
这样第三个人就可以比较前两个犯人的答案，如果前两个犯人说的数字一样，那他也说这个数字；以后的七个犯人都说这个数字，这样可以确保帽子上有重复数字的犯人回答正确；
如果第三个人发现前两个人的答案不一样，那么每个人帽子上的数据是不重复的，他也回答一个没看见的数字即可；要么说明前两个人帽子上的数字是重复的，其他八个人帽子上的数字是不重复的，那他也可以来猜自己帽子上的数是多少。
以后每个犯人的回答方法和第三个犯人一样。

作者: 迅雷还真雷 时间: 2012-5-17 11:16

所有人的数加起来，除10取余是个定值，在1到10之间，每人取一个，定有一个人取对。这个人把看到的其他人的数全加起来，除10取余。然后就可以得出自己的数了。

作者: 醉花楼 时间: 2012-5-17 11:25

数字思维不行，不知道怎么计算。只能说赦免可能非常大。各取看到的数字的总和的平均值的最相近的数

作者: tiger4u 时间: 2012-5-17 11:25

全部猜同一个数字肯定会杯具每个人都猜自己看到的数字

作者: dotchen 时间: 2012-5-17 17:56

是有办法的. 核心的问题是，一定要选择一种方式确保如果其他都错了，那么自己一定是对的。要这样做,首先犯人们自己要编好号，按照0-9编号，然后看到其他人的数字的时候，需要根据犯人的号码，以及犯人头上的号码来猜头上的数字。

这个要用到指针的概念. 每个犯人头上的数字，指向具体的犯人，一个个指针连接。例如 1头上是3，那么按照1，3排列，3头上是5 ，则为1，3，5，依次类推。对于任何一个犯人，都可以理出一个环，就是说，最后一个人头上的数字是第一个人。这样对于每个犯人而言，可以看到其他9个人，按照排列可以列出0个环或者几个环。
这里要提出一个图论的理论，也即是说，如果用指针的方式，没有重复的点数字一定在某个环中。只有重复数字的才有可能不在环中。所以方法就变得简单，就是找到所有无法成环的数字，而自己一定是加进去会构成环的人。

现在这个犯人要判断的是，有几个环，自己在哪个环里面。如果所有9个人都被归到每个环里面，那么这个犯人有两种可能，跟某个人重复数字，或者自己是不在的那个数字。这时候要猜的是那个不在的数字。举个例子，如果犯人1看到0，2，3，4，5，6，7，8，9构成了一个或者多个环，那么犯人就选1。这是因为一个环的人，可以不管其他人的号码，来确保环里面一定有人可以猜出来。具体证明可以用递归的方式，比较复杂，这里不再重复了。
现在就看那个不成环的情况怎么处理了，不成环说明自己在那个环里，或者自己就是自己的数字。在环里的人，一定会看到有个人指向自己，但是自己指向谁就不知道了。那么很简单，从指向自己的这个人开始往前推，比如说指向自己的人是3，那么要找到头上数字是3的人，再找有人头上数字是这个人的人，以此往前推，一直推到没有办法推为止。
这个时候，就会有环了，这样自己头上的这个数字就是没有办法往前推的人数字，加上他就应该是个环。
当然，必须要考虑到有重复数字的可能，这个时候的方法就是用重复数字的那个人作为起点，看最后是连接哪个人。这个里面有两种可能，一种是指向自己的重复数字，一种是不指向自己的重复数字，指向自己的重复数字，意味着自己是连接那个环的关键人物，其他人会用来推理，然后估算自己头上的环，这个时候要选择自己，因为这时候有几种可能，一种是自己加进去是个环，一种是自己是个环，如果自己加进去是个环，其他人当中一定有人推理正确。不正确的唯一可能是没有环，而没有环是不可能（根据图论），所以只有一种可能，是自己一个人构成环，也就是说自己头上就是自己的数字。

[ 本帖最后由 dotchen 于 2012-5-17 18:00 编辑 ]

作者: freeabc 时间: 2012-5-18 16:22 标题: 标题

楼上的没有太看清楚。不过能不能根据只有两个犯人或三个犯人的简化情形推演一下？

作者: ksc1 时间: 2012-5-18 16:34

让这10个人站在一起看对方帽子上的数字。只要一个人站出来，让其他9个人看，然后告诉站出来的这个人头上的号码就可以了啊。没有规定不能说话。

作者: freeabc 时间: 2012-5-18 17:08

引用:

原帖由 ksc1 于 2012-5-18 16:34 发表
让这10个人站在一起看对方帽子上的数字。只要一个人站出来，让其他9个人看，然后告诉站出来的这个人头上的号码就可以了啊。没有规定不能说话。

“彼此间无法以任何方式——包括动作表情声音眼神气味电磁场超能力等等——进行接触交流及任何信息的传递交换。”
说话属于声音的一种。

作者: 犇 时间: 2012-5-18 17:25

这十个人都不用死，九个人都报第十个人的帽子上的数字不就得了。

作者: freeabc 时间: 2012-5-18 17:30

引用:

原帖由 wghy2012 于 2012-5-18 17:25 发表
这十个人都不用死，九个人都报第十个人的帽子上的数字不就得了。

如果九个人的数字都和第十个人的不一样怎么办

作者: zengzhe21 时间: 2012-5-18 17:38

因为只要全部犯人中有一位猜对了自己帽子上的数字，则全部犯人都将给予赦免。
那么应该集合在同牢房的十个犯人，制定一方案，第一个读出他能看到的数字，后面的人全部都跟着读出同样的数字
这样就能保证有一个是正确的，全部犯人都将给予赦免。

作者: freeabc 时间: 2012-5-18 17:42

引用:

原帖由 zengzhe21 于 2012-5-18 17:38 发表
因为只要全部犯人中有一位猜对了自己帽子上的数字，则全部犯人都将给予赦免。
那么应该集合在同牢房的十个犯人，制定一方案，第一个读出他能看到的数字，后面的人全部都跟着读出同样的数字
这样就能保证有一个是正 ...

限制条件：
犯人彼此将被完全隔绝，除了能知道其他人头上帽子的数字外一无所知，彼此间无法以任何方式进行接触交流及任何信息的传递交换。每个犯人将在彼此隔绝状态下作出回答。

作者: tle521 时间: 2012-5-18 17:42

由于数字可能是在1-10之间重复，而不是每个犯人对应一个不同的数字。因此，没有能够确保生还的条件。
无论用重复报出单一数字法，跳跃报数字，无序数字法等等，都因为数字在1-10，切可能重复被推翻。
所以，只能说祝他们好运了

作者: freeabc 时间: 2012-5-18 20:35 标题: 回复 22楼的帖子

真的只能靠运气吗？那好运占多大几率呢？

作者: gzadsl1234 时间: 2012-5-20 15:55

答案很巧妙
题目中说“届时所有犯人将会被隔离”
而没有说“现在所有犯人将会被隔离”
因此，可以在发放帽子之前相互通气，分配好这么一个余数。

欢迎光临 SexInSex! Board (http://11.1y2y3y.com/bbs/)