魔方吧·中文魔方俱乐部

标题: 【fhw】我们的一道考试题 [打印本页]

作者: fhw 时间: 2012-3-29 21:38:08 标题: 【fhw】我们的一道考试题

上中学了，没有多少时间，今天好不容易上一下魔方吧，发一道我们考试出的变态题吧。

村子中有50个人，每人有一条狗,每天傍晚大家都在同一个地方遛狗。在这50条狗中有病狗(这种病不会传染)。于是人们就要找出病狗。每个人可以观察其他的49条狗，以判断它们是否生病，只有自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗，而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。第一天，第二天都没有枪响。到了第三天村子所有狗都被自己的主人杀了了，问有几条病狗，如何推算得出？
据老师说这道题很有名的~~~~~~~~~~~~~~~~~~~~有名的题都是变态~~~~~~~~~~~~~~~~~~~~~~

作者: 祭司zhangcy 时间: 2012-3-29 21:43:08

占小樊沙发我先想想；

假设只有一只病狗，那么第一天病狗的主人会发现其他49只狗狗都正常，他就可以推算出自己的狗狗是病狗，当晚杀掉；

假设共有2只病狗，其中一条病狗的主人在第一天会发现其他49只中有一条是病狗，但是第一天晚上病狗没有死掉，则第二天晚上他会杀掉自己的狗狗；

假设3条病狗，其中一条病狗的主人会在第一天发现其他49只中有2条是病狗，第一晚没有狗狗死，则病狗数量大于1，第二晚没有狗狗死，则病狗数量大于2，第三晚主人会杀掉自己的狗狗；对于健康狗狗的主人来说，他会发现其他49只中有3条病狗，第一晚没有狗狗死，则病狗数量大于1，第二晚没有狗狗死，则病狗数量大于2。。【迷茫了】

病狗的数量应该小于4.

[ 本帖最后由祭司zhangcy 于 2012-3-29 21:59 编辑 ]

作者: jimofc 时间: 2012-3-29 21:45:15

一条？？？？？？？？？？？？

作者: 石冠群 时间: 2012-3-29 21:46:07

第三天应该有三个人杀狗，怎么会杀光呢？

作者: jimofc 时间: 2012-3-29 21:50:59 标题: 回复 4# 的帖子

所以就不是3条。。。要不就是50条全病狗

作者: 绿豆糕 时间: 2012-3-29 21:56:10

应该是50条吧如果是1条到49条都会发生特殊性如果是零条那没每个人都会发现其他狗都没生病也就会推算出自己狗生病然后立即枪杀排除所以只剩下50条了

作者: 血色萱草 时间: 2012-3-29 22:18:37

让学数学的孩子告诉你，貌似答案应该是X>=3.
理由如下：
首先分析：
第一天结束，所有的人都知道病狗的数目多于1条，否则没有看到病，狗的就会在第一天杀掉自己的狗。
第二天结束，所有的人都知道病狗的数目多于2条，否则看到1条病狗的人就会杀掉自己的狗。
……
现在假设有人看到了4条病狗，则他会推论，病狗的数目=4或5，因此，最少有人看到了3条病狗。而这个人会推论至少有人会看到2条病狗，所以，会有人在第二天就推论结束，杀掉自己的狗……以此类推，得出结论，看到四条病狗的人，会在第三天得出正确或者错误的判断，在第三天杀掉自己的狗。
当X（病狗数）>=3时，按照以上推论，狗的主人都会在第三天杀掉自己的狗，并且只能判断出别人是否杀错了狗，而不知道自己是不是做出了正确的判断。

……就这样吧，表达的不是很清楚了，楼主自己理解吧……此题的关键：每个人都能做出判断，并且认为别人和自己想的一样多。

作者: 铯_猪哥恐鸣 时间: 2012-3-29 22:34:55 标题: 回复 7# 的帖子

“而不知道自己是不是做出了正确的判断” 主人只有在判断出自己的狗得病的时候才能杀了自己的狗吧。。。

作者: 血色萱草 时间: 2012-3-29 22:48:24 标题: 回复 8# 的帖子

每个人做出的判断在逻辑上都是正确的，但未必在事实上是正确的。

每个人都在自己逻辑判断的基础上推断出来自己的狗是有病的，单这个推断引用了对其他人判断的推论，因此不一定在事实上成立。

作者: 铯_猪哥恐鸣 时间: 2012-3-29 23:00:15 标题: 回复 9# 的帖子

那第一天就可以把所有狗杀死了- -|||

作者: gqc294981 时间: 2012-3-29 23:00:53

是抽屉原理吗？好像听过类似的问题不过不知道是不是抽屉原理

作者: jimofc 时间: 2012-3-29 23:04:34 标题: 回复 7# 的帖子

你那是原题分析，网上一搜一大堆。

原题是：到了第三天传来一阵枪声
这道题最后：第三天村子所有狗都被自己的主人杀了

意思不一样

作者: 血色萱草 时间: 2012-3-29 23:15:21 标题: 回复 10# 的帖子

。。。因为只有有了前两天的推论，才能知道至少X＞2啊，否则结论是不对的，X＜3，只有病狗的主人才会杀狗。

作者: superacid 时间: 2012-3-30 08:19:02

目测题目有误，不解释

作者: 洛阳狼王 时间: 2012-3-30 08:54:53

第二天应该死了两条狗才对。

作者: flwb 时间: 2012-4-1 22:46:50

这题出错了,应该是第三天响起一阵枪声,问有几条病狗,

作者: zshhsz 时间: 2012-4-2 14:17:38

大概是这道题够那些人想三天吧……
我在一本书里看过这道题，据说是IMO的，可惜没有答案。

作者: 玉逸风 时间: 2012-4-2 15:03:32

让我好好地想一想。。。。。。

作者: 心照 时间: 2012-4-2 18:02:57

题目有误，原题这里。
村子中有50个人，每人有一条狗,每天傍晚大家都在同一个地方遛狗。在这50条狗中有病狗(这种病不会传染)。于是人们就要找出病狗。每个人可以观察其他的49条狗，以判断它们是否生病，只有自己的狗不能看。观察后得到的结果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要枪毙自己的狗，而且每个人只有权利枪毙自己的狗，没有权利打死其他人的狗。第一天，第二天都没有枪响。到了第三天村子没病狗了，问有几条病狗，如何推算得出？

作者: hanxian586 时间: 2012-4-22 19:40:37

木有人得出答案吗，分享下吧~

作者: jimofc 时间: 2012-4-23 09:35:48 标题: 标题

我推理出为什么第三天所有的狗都被打死了。其实只有一条病狗，主人第一天就发现了，但不忍心打死。第二天，因为那个人没打死病狗，所以剩下的49人都做出了自己的狗也是病狗的错误判断，但他们也不忍心打死。第三天，真正病狗的主人下定决心杀狗了，其他人也都在那天决定杀掉自己的“病狗”，所以第三天晚上所有的狗都死了

作者: 一目了然 时间: 2013-3-8 10:08:34

心照发表于 2012-4-2 18:02
题目有误，原题这里。
村子中有50个人，每人有一条狗,每天傍晚大家都在同一个地方遛狗。在这50条狗中有病狗 ...

此题如此就不难解答。村民只须遵循如下原则：看见了n条病狗的主人必须在n+1天后枪毙自己的狗。事实上第一天病狗的主人看见的是2条病狗，好狗的主人看见的是3条病狗。按此原则，不管病狗是多少条都会在同一天被主人枪毙而好狗决不会受伤害。

作者: shita 时间: 2013-4-3 15:09:09

这题目是著名的脏脸博弈。答案是3条狗有病。
题目应该是这样的，50个人都知道这里有病狗，但不知道有几条。但可以观察出病狗。在观察的过程中所有人不能看自己的狗。通过推理要得知自己的狗是否有病。所有的人都会进行严格的理性的推理。
在说题目之前先说脏脸博弈。
甲乙两个人看到有人笑他们，于是看了对方一眼，互相没有反应，但是发现笑他们的人还是在笑，突然他们的脸都红了，原来他们的脸都是脏的。
1，他们看了对方的脸，知道了对方脸脏
2，但是他们都不知道自己脸脏，于是没有采取措施
3，等到反馈（就是别人笑）
4，意识到自己脸是脏的，于是脸红了。
这就是著名的脏脸博弈。

现在解题。
1，如果有一条病狗
病狗主人：第一晚就会知道自己的狗有病，于是开枪，当晚就会听到枪声
其他人：看到有1条病狗，但是不知道自己的狗是否有病，但是他知道如果自己的狗没病，第一晚会有枪声，于是他会等待。

2，如果有2条病狗
首先病狗主人会看到一条病狗，没病的狗主人会看到两条。
如果第一晚没有枪响，病狗主人就知道自己的狗有病，第二晚他会杀了自己的狗。
没有病的狗主人：看到2条病狗，而且他知道如果只有一条病狗，第一晚会有枪响，而有两条第一晚不会有枪响，而会在第2晚有枪响。因为他知道两条病狗主人会如此推理。所以当第2晚枪响的时候他就知道自己的狗没病。

3条病狗
如果看到了两条病狗，但是两个晚上都没有枪响，那么这个人就知道自己的狗有病。第三晚枪响。没有病的狗主人会看到所有三条病狗。他也知道有病的狗主人的推理。如果前两晚都没枪响，那么他就知道病狗数量至少大于2，但是他不知道自己的狗是否有病，但他知道如果有3条病狗的主人应该当晚会有措施，于是他会等待。如果当晚枪响了，他就知道自己的狗没病，否则就是自己的狗也有病，那么病狗会是4条。

宗上所述，通过脏脸博弈，答案是第3晚枪响，那么就有3条病狗。

作者: shita 时间: 2013-4-3 15:12:04

gqc294981 发表于 2012-3-29 23:00
是抽屉原理吗？好像听过类似的问题不过不知道是不是抽屉原理

是脏脸博弈，是博弈推理题

作者: shita 时间: 2013-4-3 15:13:39

是很有名的，我给你解答了，或许解答的答案你已经不需要了

作者: mamee 时间: 2013-4-17 13:11:48

要是我回家就把自己的狗搞死。。。。不过我也觉得病狗大于等于3

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