【集思广益】一道真正的智力题，据说是目前世界上最好的智力题目。

胖子多多

好的智力题目的标准是：1、一般人做不出来或者做不下去。2、不需要知识。

题目：
　　　　有十二个乒乓球特征相同，其中只有一个重量异常，现在要求用一部没有砝码的天平称三次，将那个重量异常的球找出来。
　　　　
评分标准：
　　　　1、30分钟以内做出来：智力很高很高很高，不知道有多高。
　　　　2、60分钟以内做出来：智力很高。
　　　　3、两小时内做出来：　智力相当高。
　　　　4、1天或者1周内做出来：智力也很高，而且还是一个有毅力的人。
　　　　5、10分钟内做出来：你或者以前做过，或者多半是个马虎的人。回去检查答案。
            6、算出一种答案也不要太高兴了，还有至少5种方法等着你去想呢
            7、找到了6种方法也不要太得意，还有第七种方法呢
            8、当然最周详、全面的答案，我暂时只找到了98（338）种。你能再补充些吗？
--------------------------------------------------------------------------------
*~*提醒一下，题目中的隐含信息，“重量异常”，可没说它到底是重还是轻，怎么办自己想，难点也就所在。省得有人看不见，错认为很easy。


注：我说的答案是指不同的方法。并不是说先拿哪个球，后拿哪个球，球不一样就算是两种方法啦。那样也没有什么任何的实际意义。我发帖的目的在于多寻些可行的方法以补充自己的思维。愿意动脑筋的朋友，欢迎都来试一下。

声明：*.*此题不能能验证一个人的智商，纯粹是个小游戏，其他别无用处。

谁哪能搞出第八种方案啊？我这里有七个……

[ Last edited by 胖子多多 on 2004-12-31 at 10:18 ]

zjmzqq

不是那么难吧
不到一分钟都能想明白的事情

胖子多多

QUOTE:

Originally posted by zjmzqq at 2004-12-30 06:40 PM:
不是那么难吧
不到一分钟都能想明白的事情

呵呵，我猜你恐怕就是第五种人吧
提醒一下，题目中的隐含信息，省得有人看不见，错认为很easy，自己不含糊呢。;)

“重量异常”，可没说它到底是重还是轻，难点也就所在。

zjmzqq

晕
真的马虎了**\
这题目有点BT了

steven1900

请楼主自觉查找以前的帖子,答案早就有了的.

johnlions

我就是用30分钟左右作出来的，而且和标准答案不一样。
可是现在一个offer都没有，sigh, 智力~~~

vc1018

不可能吧

胖子多多

QUOTE:

Originally posted by steven1900 at 2004-12-30 07:40 PM:
请楼主自觉查找以前的帖子,答案早就有了的.

哦？我初来咋到，还请多担待。听你的话，我去查了一下，封存区里确实是有，谢谢你啦。我看了一下，那里已有公布的答案，确是对的。
不过，我这里有5种该题的答案，皆为正解，是我自己想出来的，所以多少对此题还是有点发言权的。发帖主要是想看看还有没有其他的解法。哪位同仁，若是也想挑战极限的话，请一同继续参与下去……共同讨论、共同进步嘛。

注：我说的答案是指不同的方法。并不是说先拿哪个球，后拿哪个球，球不一样就算是两种方法啦。那样也没有任何的实际意义。

ps：还希望版主不要认为我这个帖子是灌水贴，删了。在此谢谢啦
先祝大家元旦快乐了

龙睛鱼

上初中的时候就做过了。用了笔和纸。30分钟左右出的答案。不用比和纸光想的话，可能需要更多的时间的。用比和纸画画，其实还是比较简单的问题。

胖子多多

QUOTE:

Originally posted by zjmzqq at 2004-12-30 07:13 PM:
晕
真的马虎了**\
这题目有点BT了

呵呵，我平时也老爱马虎……和你一样。没事，多想想，蛮有意思的一道题。

月光疾风

很早以前就看过
这个有什么难的啊

zjmzqq

QUOTE:

Originally posted by steven1900 at 2004-12-30 19:40:
请楼主自觉查找以前的帖子,答案早就有了的.

哥们放毒了*~**.*lll
害我忍不住去翻了老贴*.*
惭愧惭愧^.^l

**\**\**\**\

twb

我从没看过此体．但3分钟就想出了答案．还不知有多聪明．．太夸张了吧？

胖子多多

一个月后公布我这里有的所有答案～～

[ Last edited by 胖子多多 on 2004-12-30 at 22:17 ]

ljmwyh

先称8个，没有再称后面4个里的2个，最后比对剩下的2个，三次出结果了

kkqq

先六-六称，重的一方再三-三称，又重的一方一-一称，哪个球重就是哪个，若相同，剩下的那个就是，共三次出结果。想了2分钟，出答案。看来是个马虎人？

johnlions

楼上的两个都不对。
还是好好看看题目吧。

月光疾风

有７种方法！？

胖子多多

QUOTE:

Originally posted by 月光疾风 at 2004-12-30 11:24 PM:
有７种方法！？

或者说还不止七种呢。若是考虑到第二次称量后，肯定有三种结果，其中两个结果第三次称量时每个又都可以有两种不同的方法，那也可以算是2×2种，顾也可以说是有四种方法，若是这样7种就可以算成13种了。不过，我这为了不混淆试听，姑且先算是两种。一共有3类这样的情况。加上一种特殊的排列方法，共七种。;)

龙睛鱼

这帖中又引诱出了许多马虎人啊。。。。。。。。。。哈哈哈哈哈哈。

yoodpo

以前算过，现在不愿意费脑袋想

胖子多多

QUOTE:

Originally posted by 胖子多多 at 2004-12-31 12:07 AM:


或者说还不止七种呢。若是考虑到第二次称量后，肯定有三种结果，其中两个结果第三次称量时每个又都可以有两种不同的方法，那也可以算是2×2种，顾也可以说是有四种方法，若是这样7种就可以算成13种了。不过， ...

昨天睡觉前，我又琢磨了一下，第一次称量后有三种结果，我以上只是考虑了一种结果的第二次、第三次称量的情况，若是考虑到第一次称量后三种不同结果分别发展下去，每种结果也都还能有不同的组合。如第一次相等，测剩下4个球的方法就有2种。同样，第一次测量后第二种不平的结果也如上应该有至少7种，若考虑到系统中，各个组成元素排列顺序的唯一认证性，也可以认为是有13种的。
哪样至少就会有13×2×13＝338种成立的解题方法。若是只考虑单元素单组合性，那么就至少有7×2×7＝98种成立的解题方法。

继续思考中……

afire

QUOTE:

Originally posted by 月光疾风 at 2004-12-30 08:48 PM:
很早以前就看过
这个有什么难的啊

都说部难，我就部想了。

sigh

火星啦~ 咱们这里有朋友发过，好像在娱乐区发的

其实只要想出第一种方法，其他的方法就比较容易想出来了。

pk

记得当时只想出来了1种－－再没有想还有其他方法了……

yogibear

明年再想，现在不想想了。

flyfrog

这个问题很老了
没记错的话方法其实只有一种，已经数学上证明了的
所有已知方法都等价

张书锋

首先这个题不能用一般的简单的单独二进制编码方法解出，因为计
算这些小球的墒，log2（12）>3，在实际中取整数，所以，如果用
一般的编码方法，或者二叉树来解答，必然需要4次才能找出正确
答案。那么，这个题里面一定有个trick，而这个trick就在于信息
的联合编码。由信息理论，我们知道，获取信息之间的统计相关性，
得到的entropy rate是小于单独编码的entropy的。

以上分析对了实际解题仍然没有直接帮助，只是帮我们确定了一点，
那就是不能单独的把分组的球进行比较，比较，再比较，而需要在
某一个步骤里面把前面得到的信息和未知信息糅合起来考虑。幸好
只有三布，我们可以慢慢试探。

至少有两种编码可以比较接近最终答案，一种是一开始分为4组，每
组3个，一种是一开始分为三组，每组4个。第一种方法，最后归结为
在3个小球里面找出未知轻重属性的异常小球，很可惜，在一次里面
无论如何不能完成，信息太少。第二种最后归结为在8个小球里面找出
未知轻重属性的，但是知道4个一组轻重属性的小球，这组情况有更多
联合信息，采用。

具体解法如下：

分为4个一组，三组，A，B，C，比较A，B，重量如果一样，异常球
在C，把C分为2个一组两组，D，E，从A/B取两个标准球和D比较，1)
如果重量一样，异常球在E，再取一个标准球和E中任何一个比较，
重量不一样则找到异常球，重量一样则异常球为剩下E中一个；2)如
果重量不一样，则异常球在D，剩下步骤同上。

以上步骤很简单，很容易想到，学过哈夫曼编码的可以画出这个编码
图，10分钟以内轻松得解。但是，独立的哈夫曼编码不能解决一开始
提到的问题。有点技巧的是下面：

如果A，B重量不一样，那么异常球在A或者B，此时记下A，B的轻重关
系（这是数据之间的统计冗余联系，后面会用到），比如B重，然后
把A组拆为另外两组，F，H，每组两个，再在B中随便取两个，给F，H
每组添加一个，构成新组F'，H’,现在比较两组重量，如果重量一样，
异常球在B组剩下的两个小球里面，只需要用标准球和任何一个比较一
次即可找出异常球。如果重量不一样，记下此时轻重关系，比如H'比F'
重，那么只有可能有两种可能：1)H'中来自B组的小球较重，是异常球。
2）F’中来自F，也就是原来A组的两个小球的一个较轻，是异常球。
现在把这三个取出来，编号X，Y(来自A），Z（来自B），再比较X，Y，
如果重量一样，则Z为异常，如果不一样，用已知轻重关系，较轻的小
球为异常球（因为X，Y只可能存在较轻的球）。

以上只是举了B重的一种情况，如果B轻，完全类似的推导过程。

我一开始想分为4组，花了10分钟，最后在3个小球判断一个卡住了，耗
时10分钟，然后分为三组，前面部分5分钟轻松解决，最后部分耗时10分
钟。信息的联合处理是解决本题的关键。没有学过信息论的同学，如果
能够在30分钟以内解出来，确实很不容易，但我不是，呵呵。

张书锋

我是不是有点不厚道？

月光疾风

QUOTE:

Originally posted by 胖子多多 at 2004-12-31 10:12:


昨天睡觉前，我又琢磨了一下，第一次称量后有三种结果，我以上只是考虑了一种结果的第二次、第三次称量的情况，若是考虑到第一次称量后三种不同结果分别发展下去，每种结果也都还能有不同的组合。如第一次相等，测剩下4个球的方法就有2种。同样，第一次测量后第二种不平的结果也如上应该有至少7种，若考虑到系统中，各个组成元素排列顺序的唯一认证性，也可以认为是有13种的。
哪样至少就会有13×2×13＝338种成立的解题方法。若是只考虑单元素单组合性，那么就至少有7×2×7＝98种成立的解题方法。

继续思考中……

越听越邪乎了