浆糊论坛-RO小站 - Powered by Discuz! Board

标题: 问一个智力题，网上找不到确切答案的 [打印本页]

作者: zxoys 时间: 2009-10-7 19:47 标题: 问一个智力题，网上找不到确切答案的

有100个人与鬼，从外表很难区分开来。
只知道其中人的个数超过半数，剩下的都是鬼，而人只说真话，鬼可能说真话也可能说假话。
这100个人（鬼）互相都知道彼此是人还是鬼。
现在要你从这100个人（鬼）当中找出一个人来，只能通过以下方式：
每次挑出两位，让这两位互相说出对方的身份，你根据两位的话进行判断。
问要最快的找出一个人来，至少要多少次？(一定要考虑最坏的情况)

100个人与鬼，说的是人的数+鬼的数一共等于100。此题非脑急题~~。

ps：这题有点难度，大家弄清题意后，再好好想想

可以的话，说出你的算法

作者: 々风妖々 时间: 2009-10-7 19:53

已知人的数量大于鬼的数量并且占总体数量50%以上.也就是说,人的数量最少为51,最多为99,而鬼的数量最多为49,最少为1.

设想1:

因为条件限制一次只能选出两人进行询问,那么设两个为"X/Y",则可能出现的答案有:

1、X为鬼并且说谎,Y为鬼并且说谎,答案为:人、人.
2、X为鬼并且说真话,Y为鬼并且说真话,答案为:鬼、鬼.
3、X为鬼并且说谎,Y为鬼并且说真话,答案为:人、鬼.
4、X为人,Y为人,答案为:人、人.
5、X为鬼并说谎,Y为人,答案为:鬼、鬼
6、X为鬼并说真话,Y为人,答案为:人、鬼

结论:不论出现何种答案,其中一个都可能是"鬼",所以随机的询问是无法找到确定的"人"的.

推翻

设想2:

此题无解

这是一道相当变态的题目,一定程度上等于一道已知条件为:

X+Y=100

X>Y

X和Y都为正整数.

求X或Y的题目,我不知道当一个只有三个数字的等式中两个都为未知数的情况下要怎么样解.而且最恶心的地方是鬼不仅数量不明,还可能说真话可能说谎话,这样完全就不能以鬼的答案作为条件.作为求证,给出的结论必须是经得起最坏情况的考验的,那么如果有49个鬼的话,则100人中有49个答案不能作为条件,并且还不能确认这49个答案究竟是其中第几个答案.也就是说不管你怎么问,也无法得知任何一点可以作为定论的条件.

推翻,我的斗志是不灭的,对我的智商是有绝对自信的..

设想3:

随机的挑选出其中一个,并设其为"X"

依次询问其余99个,根据已知条件"人的数量大于鬼".于是可能得出的答案有:

1、当X为人时,回答X为"人"的数量一定大于等于50.
2、当X为人时,回答X为"鬼"的数量一定小于50.
3、当X为鬼时,回答X为"人"的数量一定小于50.
4、当X为鬼时,回答X为"鬼"的数量一定大于等于50.

结论:

1、当回答X为"人"的数量大于等于50时,X一定为人.
2、当回答X为"鬼"的数量大于等于50时,X一定为鬼.

这个设想最终是可以得到准确答案的.

结论!

答案是:

最少需要询问的次数为:连续50个回答X为"人"时,则可以确认X为"人",询问的次数为50

更正了最坏的情况需要询问的次数....

最多需要询问的次数为:当有超过50个回答X为"鬼"时,则确认X为鬼.因为是最坏的情况,考虑到需要询问99次才能够得到这个结论.于是将X排除,在余下的99个之中重新设一个"X",按照步骤继续询问,需要98次询问得到X为"鬼"的结论.按照这个方法持续下去.因为鬼最终的数量只有49个,当排除了49个鬼之后余下的51个便都是人了.

于是询问的次数为:

99+98+97+96+95+94........+53+2

=(100*10+90*10+80*10+70*10+60*7)-[4(1+2+3+4+5+6+7+8+9+10)+(1+2+3+4+5+6+7)]+2

=(1000+900+800+700+420)-[4*55+28]+2

=3820-[220+28]+2

=3820-248+2

=3572+2

=3574

至于为什么算式最后是+2而不是+52呢,因为当剩下最后1个鬼和51个人总数为52时,从中设一个X.只需要询问其中两个关于X的身份,而只可能出现如下几种情况:

1、两个都回答"人",那么X必定是人,因为只剩下一个鬼,不论他的答案真话还是假话,第二个答案必定是真的.
2、两个都回答"鬼",那么X必定是鬼,而因为唯一剩下的鬼被设为了X,于是剩下的51人必定全都是人,就不用再问了.
3、一个答"鬼",一个答"人",因为人必定说真话,而会说假话的只有鬼,所以出现不同答案的话必定有一个是假话,也就是说他们两个之中有一个是鬼,而鬼只剩下了一个,所以X必定是人.

于是,最多的询问次数应该为3574次...

P.S:鄙视楼下的..

[ 本帖最后由々风妖々于 2009-10-7 23:51 编辑 ]

作者: moli 时间: 2009-10-7 20:06

同楼上...

作者: minagetsu 时间: 2009-10-7 20:41

= =不会

作者: 々风妖々 时间: 2009-10-7 21:13

已解,LZ放出答案吧.........

[ 本帖最后由々风妖々于 2009-10-7 21:37 编辑 ]

作者: zxoys 时间: 2009-10-7 21:43

我之前也在计算中，分析到一个结论，随机的挑选出其中一个,并设其为"X"
第一次筛选中，第50个说他是人的，他一定是人，第50个说他是鬼的，一定是鬼
如果选中的是鬼，那么下次筛选可以去掉一个鬼
个人分析：
如果抓到的是人，最多说他是鬼49次，之后都是说人
如果抓到的是鬼，最多说他是人48次，之后都是说鬼
如果抓到的是人，最多说他是人50次，第50个说他是人的一定是人
如果抓到的是鬼，最多说他是鬼99次，第50个说他是鬼的一定是鬼，之后的人可以全排除，把剩下的重新排
最坏的情况，第99次听到第50个鬼，说人的都可以排除，突然想到，其实最多100次就能排查出来
在确定自己手里是鬼的前提下，之前说他是人的都可以排除了

如果鬼也说真话来隐藏自己的话
再排查下个
应该是50+49+。。。+2=1274次

[ 本帖最后由 zxoys 于 2009-10-8 15:36 编辑 ]

作者: 々风妖々 时间: 2009-10-7 21:47

原帖由 zxoys 于 2009-10-7 21:43 发表
我之前也在计算中，分析到一个结论，随机的挑选出其中一个,并设其为"X"
第一次筛选中，第50个说他是人的，他一定是人，第50个说他是鬼的，一定是鬼
如果选中的是鬼，那么下次筛选可以去掉一个鬼
从99人开始
...

最多需要询问的次数为:当出现"人"和"鬼"的答案的次数都刚好为49时,根据已知条件"人的数量大于鬼",那么剩下的那一个必定是人,也就是说最多只需要询问98次.

最多为98次哦~~

你的推论跟我最开始的看法相似,这样排除的话需要做99*49=4801次询问.

[ 本帖最后由々风妖々于 2009-10-7 21:49 编辑 ]

作者: minagetsu 时间: 2009-10-7 21:58

风妖酱乃好厉害···[m_装可爱] 同时咱发现乃也很闲··咱要把RPG的帖子顶上来给你一点压力了··

作者: 々风妖々 时间: 2009-10-7 22:00

原帖由 minagetsu 于 2009-10-7 21:58 发表
风妖酱乃好厉害···[m_装可爱] 同时咱发现乃也很闲··咱要把RPG的帖子顶上来给你一点压力了··

其实我一直在做啊..没有松懈哦..

作者: zxoys 时间: 2009-10-7 22:17

个人分析：
如果抓到的是人，最多说他是鬼49次，之后都是说人
如果抓到的是鬼，最多说他是人48次，之后都是说鬼
如果抓到的是人，最多说他是人50次，第50个说他是人的一定是人
如果抓到的是鬼，最多说他是鬼99次，第50个说他是鬼的一定是鬼，之后的人可以全排除，把剩下的重新排
最坏的情况，第99次听到第50个鬼，说人的都可以排除，再算

从99个开始，这时鬼最多48个，又很不幸，又只排除了他，本次筛选98次
从98个开始，这时鬼最多47个，又很不幸，又只排除了他，本次筛选97次
从97个开始，这时鬼最多46个，又很不幸，又只排除了他，本次筛选96次
从96个开始，这时鬼最多45个，又很不幸，又只排除了他，本次筛选95次
从95个开始，这时鬼最多44个，又很不幸，又只排除了他，本次筛选94次
。。。。。

如果每次都是鬼，其他都未知道

再算算

[ 本帖最后由 zxoys 于 2009-10-7 22:45 编辑 ]

作者: 半根冰棍 时间: 2009-10-7 22:20

一直抽到鬼这辈子也别想完了

作者: zxoys 时间: 2009-10-7 22:23

原帖由 半根冰棍 于 2009-10-7 22:20 发表
一直抽到鬼这辈子也别想完了

每次抽到鬼，可以把鬼排除

作者: 半根冰棍 时间: 2009-10-7 22:28

问题是鬼说的不知道真话还是假话..　要是只说假话还可以排除吧..

作者: minagetsu 时间: 2009-10-7 22:30

[m_害羞] 要随时预报进度嘛

作者: 半根冰棍 时间: 2009-10-7 22:31

噢我懂了...　不是随机选择２个人..

作者: 々风妖々 时间: 2009-10-7 22:43

我说,你们不要都无视我的答案啊.........

作者: zxoys 时间: 2009-10-7 22:43

原帖由 zxoys 于 2009-10-7 22:17 发表
个人分析：
如果抓到的是人，最多说他是鬼49次，之后都是说人
如果抓到的是鬼，最多说他是人48次，之后都是说鬼
如果抓到的是人，最多说他是人50次，第50个说他是人的一定是人
如果抓到的是鬼，最多说他是鬼 ...

只剩下一个鬼时总数是52个
分析：51+52+53+54+。。。+99=？

作者: zxoys 时间: 2009-10-7 22:48

我的分析是最糟糕，最倒霉的情况下筛选7200次后剩下的都是人了，鬼全部被排除掉了

[ 本帖最后由 zxoys 于 2009-10-7 22:56 编辑 ]

作者: zxoys 时间: 2009-10-7 22:56

原帖由 々风妖々 于 2009-10-7 22:43 发表
我说,你们不要都无视我的答案啊.........

你的答案我都有仔细看的，没无视，同时自己也想，不知道谁的更正确，等高人来指点

作者: 天才小猪 时间: 2009-10-7 23:09

如果是要最快那就是50次就搞掂了

作者: zxoys 时间: 2009-10-7 23:22

原帖由 天才小猪 于 2009-10-7 23:09 发表
如果是要最快那就是50次就搞掂了

我答案是50~7200次之间，最倒霉，最糟糕的情况下7200次

作者: 々风妖々 时间: 2009-10-7 23:51

原帖由 zxoys 于 2009-10-7 23:22 发表

我答案是50~7200次之间，最倒霉，最糟糕的情况下7200次

仔细想了想,我的答案有误..更新一下..

最多需要询问的次数为:当有超过50个回答X为"鬼"时,则确认X为鬼.因为是最坏的情况,考虑到需要询问99次才能够得到这个结论.于是将X排除,在余下的99个之中重新设一个"X",按照步骤继续询问,需要98次询问得到X为"鬼"的结论.按照这个方法持续下去.因为鬼最终的数量只有49个,当排除了49个鬼之后余下的51个便都是人了.

于是询问的次数为:

99+98+97+96+95+94........+53+2

=(100*10+90*10+80*10+70*10+60*7)-[4(1+2+3+4+5+6+7+8+9+10)+(1+2+3+4+5+6+7)]+2

=(1000+900+800+700+420)-[4*55+28]+2

=3820-[220+28]+2

=3820-248+2

=3572+2

=3574

至于为什么算式最后是+2而不是+52呢,因为当剩下最后1个鬼和51个人总数为52时,从中设一个X.只需要询问其中两个关于X的身份,而只可能出现如下几种情况:

1、两个都回答"人",那么X必定是人,因为只剩下一个鬼,不论他的答案真话还是假话,第二个答案必定是真的.
2、两个都回答"鬼",那么X必定是鬼,而因为唯一剩下的鬼被设为了X,于是剩下的51人必定全都是人,就不用再问了.
3、一个答"鬼",一个答"人",因为人必定说真话,而会说假话的只有鬼,所以出现不同答案的话必定有一个是假话,也就是说他们两个之中有一个是鬼,而鬼只剩下了一个,所以X必定是人.

于是,最多的询问次数应该为3574次...

作者: zxoys 时间: 2009-10-8 00:10

过来汗一下自己的数学水平，全还给老师了

作者: 拽→强 时间: 2009-10-8 13:13

最糟糕的是其实只有1个鬼而且只会说假话你一辈子都找不出

作者: 々风妖々 时间: 2009-10-8 14:09

原帖由 拽→强 于 2009-10-8 13:13 发表
最糟糕的是其实只有1个鬼而且只会说假话你一辈子都找不出

假如只有一个鬼,并且只说假话的话那就好找了..

随便设一个X,出现两种情况.

X为人的话,询问另外的99个而其中只有一个答案不一样(因为鬼只说假话..)

X为鬼的话,询问另外的99个中的2个,那么两个答案都将会是"鬼",因为人只说真话.

那么,最好的情况下X为鬼,只需要问2次.

最坏的情况是把人设为了X,那么需要问99次...

相对的,如果鬼只说真话,就比较麻烦一点,不过因为人也是只说真话的,把他们分成50组,每组两人,互相问就知道了.

所以最好的情况是问1次,最坏的情况是问50次...

本身这道题最难的地方就在于鬼不一定说真话,也不一定说假话..

作者: zxoys 时间: 2009-10-8 14:44

突然想到，其实最多100次就能排查出来
在确定自己手里是鬼的前提下，之前说他是人的都可以排除了

[ 本帖最后由 zxoys 于 2009-10-8 14:49 编辑 ]

作者: linjinghui 时间: 2009-10-8 14:47

作者: siro 时间: 2009-10-8 14:51

这题目怎么这么象雷顿教授。。。

作者: zxoys 时间: 2009-10-8 14:51

如果鬼也说真话来隐藏自己的话
再排查下个
应该是50+49+。。。+2=1274次

[ 本帖最后由 zxoys 于 2009-10-8 15:32 编辑 ]

作者: zxoys 时间: 2009-10-8 15:35

个人分析：
如果抓到的是人，最多说他是鬼49次，之后都是说人
如果抓到的是鬼，最多说他是人48次，之后都是说鬼
如果抓到的是人，最多说他是人50次，第50个说他是人的一定是人
如果抓到的是鬼，最多说他是鬼99次，第50个说他是鬼的一定是鬼，之后的人可以全排除，把剩下的重新排
最坏的情况，第99次听到第50个鬼，说人的都可以排除，突然想到，其实最多100次就能排查出来
在确定自己手里是鬼的前提下，之前说他是人的都可以排除了

如果鬼也说真话来隐藏自己的话
再排查下个
应该是50+49+。。。+2=1274次

作者: 与星独白 时间: 2009-10-8 15:37

答案
3+5+……+49=624

分析

抽出两个人问话  会有3种情况:

1.两者都说对方是人                推论:两者都是人或两者都是鬼
2.两者都说对方是鬼                推论:两者都是鬼或一人一鬼
3.一人说对方是人一人说对方是鬼    推论:同上

由上分析可知:双方都是人的情况只有情况1..

故  将出现情况2和情况3的两人都排除..

此时  人鬼数量都为偶数  并被你的抽取而两两分组

这样便可以采用"拆对造单"的思想来进行排除,进而缩小取值范围

步骤

最差的情况是原100个中52人48鬼

从100人(鬼)中随机舍去一个,然后随机抽取两个问话

抽到的情况最差的是只有一对问话是情况2或3

另外还剩一人  将剩下一人也舍去

此时问话49次舍去4者  还剩28组

接下来重复以上步骤

全部最差情况每次只舍去4这计算

最后一次剩3组人  1组鬼

问话3次  舍去2人2鬼  剩下4个全是人

故  根据等差数列求和得: 3+5+...+49=624

-------------------------------------------------------------------------------------

不知道有没错

最近数分和C程学的我头晕..

作者: 々风妖々 时间: 2009-10-8 23:39

求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内.

作者: zxoys 时间: 2009-10-9 11:45

原帖由 々风妖々 于 2009-10-8 23:39 发表
求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内.

我也是突然想到的，你的算法，在最多第99次时，说假话的鬼会被暴露身份，因为人是不会说假话的，因为确定了自己手里的是鬼，那么说他是人的，岂不是都是鬼？
所以鬼只能说真话才能隐藏自己

作者: zxoys 时间: 2009-10-9 11:52

原帖由 々风妖々 于 2009-10-8 23:39 发表
求的不是"绝对"吗......因为鬼可能说真话,也可能说假话,不确定性的因素就不能计算在内.

从计算的角度，你的算法是正确的，开始我也觉得是对的，但不知道为什么老让我有种哪里出错的感觉，后来突然想到，从现实角度就不对了

作者: 与星独白 时间: 2009-10-9 12:19

你们两个无视我

作者: zxoys 时间: 2009-10-9 15:23

原帖由 与星独白 于 2009-10-9 12:19 发表
你们两个无视我

你的算法没看懂，能说的浅显点不？

作者: 天才小猪 时间: 2009-10-9 21:30

如果要算最糟糕的情况就是有49个鬼
而且他们都是在说假话
而你前面49次抽到的都是鬼
所以你最遭要问的次数就是99+98+97+96+……+50=3725次

作者: 与星独白 时间: 2009-10-9 21:42

原帖由 zxoys 于 2009-10-9 15:23 发表

你的算法没看懂，能说的浅显点不？

分组啊.. 两个一组

作者: zxoys 时间: 2009-10-10 20:27

原帖由 与星独白 于 2009-10-9 21:42 发表

分组啊.. 两个一组

如果是52和48，又偏偏都是人和人配，鬼和鬼配，鬼永远说对方是人，怎么办？

作者: zxoys 时间: 2009-10-10 20:29

原帖由 天才小猪 于 2009-10-9 21:30 发表
如果要算最糟糕的情况就是有49个鬼
而且他们都是在说假话
而你前面49次抽到的都是鬼
所以你最遭要问的次数就是99+98+97+96+……+50=3725次

这种算法不对，这样在第一轮就可以把说假话的鬼给排除掉了，你的方法只要100次就能把所有鬼排除，所以不是最糟糕的

作者: 天才小猪 时间: 2009-10-11 14:21

那就换一下
最糟糕的情况就是有49个鬼
而且他们都是在说真话
而你前面49次抽到的都是鬼
那就是49×50=2450？

作者: zxoys 时间: 2009-10-11 14:34

原帖由 天才小猪 于 2009-10-11 14:21 发表
那就换一下
最糟糕的情况就是有49个鬼
而且他们都是在说真话
而你前面49次抽到的都是鬼
那就是49×50=2450？

每一轮可以排除一个鬼，所以是50+49+。。。。+2=1724次
为什么第一个是50呢，因为100个人（鬼）时要排查50次，确定一个鬼，然后去掉这个鬼，又从99个人（鬼）开始

作者: 天才小猪 时间: 2009-10-12 21:21

就算剩下51个人（鬼）
但是你还是要问完50次才能确定你问的那个是人还是鬼

作者: yinyin8023 时间: 2009-10-13 12:13

问要最快的找出一个人来，至少要多少次？(一定要考虑最坏的情况)

是不是有些矛盾？要最快问的是至少，但又要考虑最坏的情况，那不是至多吗？

作者: 与星独白 时间: 2009-10-14 13:18

原帖由 zxoys 于 2009-10-10 20:27 发表

如果是52和48，又偏偏都是人和人配，鬼和鬼配，鬼永远说对方是人，怎么办？

最坏的情况就是52和48  这种情况一开始就踢掉一个  然后再按组抽  剩下的一个不用管他是人是鬼也都踢掉

鬼永远说对方是人无所谓  只要对方是人就肯定说你是鬼

在抽出的两个中  只要有一者说对方是鬼就把两个都踢掉

这样大胆踢掉不用担心人全部被你踢完  因为人比鬼多

作者: 人生若只如初见 时间: 2009-10-14 15:39

风妖很好很强大，我看完题目已经晕了，数学白痴路过围观

作者: zxoys 时间: 2009-10-14 22:47

原帖由 天才小猪 于 2009-10-12 21:21 发表
就算剩下51个人（鬼）
但是你还是要问完50次才能确定你问的那个是人还是鬼

人比鬼多，鬼的最大基数最大不会超过49，所以问50次，同理问完一轮去掉一个鬼后，最大基数不会大于48，也就是问49次就能确定

作者: zxoys 时间: 2009-10-14 22:50

原帖由 与星独白 于 2009-10-14 13:18 发表

最坏的情况就是52和48  这种情况一开始就踢掉一个  然后再按组抽  剩下的一个不用管他是人是鬼也都踢掉

鬼永远说对方是人无所谓  只要对方是人就肯定说你是鬼

在抽出的两个中  只要有一者说对方是鬼就 ...

你这方法在人51鬼49这种单数情况下，怎么确定？因为并不能确定人和鬼的确切数字，除了知道人比鬼多外，并不知道确切数字的，所以假设情况下要考虑偶数和奇数都能适用

作者: 与星独白 时间: 2009-10-16 22:19

原帖由 zxoys 于 2009-10-14 22:50 发表

你这方法在人51鬼49这种单数情况下，怎么确定？因为并不能确定人和鬼的确切数字，除了知道人比鬼多外，并不知道确切数字的，所以假设情况下要考虑偶数和奇数都能适用

为什么不能用

用同样的方法

第一轮结束后就自动成对分组了

你自己想想是不是

用我剔除法  可以保证人和鬼的数目都是成对的

而且如果是人人组合的绝对不会被剔只有人鬼和鬼鬼组合会被剔

这样保证了每次剔除的人的数目不会比鬼多  最多和鬼一样

那样剔到最后肯定只剩人了

欢迎光临浆糊论坛-RO小站 (http://bbs.rohome.cn/)