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

胖子多多

QUOTE:

Originally posted by 张书锋 at 2005-1-1 12:40 AM:
首先这个题不能用一般的简单的单独二进制编码方法解出，因为计
算这些小球的墒，log2（12）>3，在实际中取整数，所以，如果用
一般的编码方法，或者二叉树来解答，必然需要4次才能找出正确
答案。那么， ...

终于遇到高手了，可以上升到理论的层面上了，果然是更剩一筹。你是来自清华大学物理系的啊？难怪这么专业嘛……

我本科学的是企业管理，和数学、物理也都只是在高中的时候打过几年交道，看了你写理论应用，感觉茅塞顿开，也许我用不了什么特别专业的术语，但意思是可以理解和表达的，想法也是可以扩展的。算是殊途同归吧

胖子多多

QUOTE:

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

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

二进制却是用不了，因为一次天平称量会有三种直接结果，左倾、右倾、平衡，而前两种有包含着一组相关的隐含信息，如左倾，则重球在左盘子里or轻球在右盘中。这是得到结果，反推其形成的原因，管理学中就经常会应用到此法，每次我都喜欢，先分段、后赋值、再加权平均，若是纯理论探讨其中赋值可ram，用电脑程序多次运算得出一个概率值，做最后的分析、评估依据用。扯远了～

二叉树只能对是否两种情况来进行判断，计算机的语言，若对于多结果好像还得变型一下才能用。mba的逻辑课中倒是有决策树的训练，倒是很有助于一个人的思维逻辑能力，此题也有这方面的涉及，很有意思的。

胖子多多

QUOTE:

Originally posted by 张书锋 at 2005-1-1 12:40 AM:
首先这个题不能用一般的简单的单独二进制编码方法解出，因为计
算这些小球的墒，log2（12）>3，在实际中取整数，所以，如果用
一般的编码方法，或者二叉树来解答，必然需要4次才能找出正确
答案。那么， ...

看了一眼，你说的方法可行。语言也算是简练，直接，我倒是觉得还有进一步提升的空间。我不是托大，原本我写的更罗嗦，看过好多人写出的答案，才发现，这行文的逻辑顺序、赋标及语言的简洁也都是一门功夫，在这方面也是应该好好训练学习的，平常若是能听到那种精彩的讲座，便不难理解为什么有的人会那么快的就有了那么大的成就，沟通的确是一种能力，更是一种本领，值得花精力和时间去雕琢和研讨的。

胖子多多

QUOTE:

Originally posted by flyfrog at 2005-1-1 12:33 AM:
这个问题很老了
没记错的话方法其实只有一种，已经数学上证明了的
所有已知方法都等价

解题思路可能是只有一种，可具体的方法却不是这样的。记得大学时学概率论时，有个乘法原理：设完成一件事有n个步骤（仅当n个步骤都完成了，才能算是完成了这件事），若第1步有m1种方法，第2步有m2种方法……第n步有mn种方法，则完成这件事共有M＝m1×m2×……×mn种方法。这是我的理论依据，下面我再举例证明自己的观点，拿此题为例。

选个最简单步骤，证明一下至少有两种方法可以成立，同时它们也不等价。
第一次称量，试验中一种结果是天平平衡。结论：异重球只能在剩余的四个球中（简称c4个）。第二步第一种方法， 拿c2个与8个好球中的2个比较，若平，则再……；若不平，则再……。第二步第二种方法，拿c3个球和8个好球中的3个比较，若不平，则从这c3个拿出任何两个称重，再平，则……；再不平，则依照天平倾斜的方向判断哪个球是异重量的，以第二次称量偏向为依据。同样也可以找的出异重量的球。

以上的解法恐怕要算两种方法吧。其实第一次称重不平，左倾or右倾的情况更加的复杂，至少有三类、七种组合可以成立，当然这都没有算七种中有六种第三步的两种情况，否则就是十三种组合了。那么，左倾和右倾若是且的关系，找的是一种多可能性的组合嘛，则总共的组合方法就应该是13×2×13＝338个啦。接着找下去，没准还有……

[ Last edited by 胖子多多 on 2005-1-1 at 11:14 ]

flywater

首先考虑有没有可能，称三次，每次
可能的结果是左重，右重，一样重，三种，
那么相当于对应27种可能性，而12个球，
坏球可能重可能轻，则只有24种可能，故
一定可以找出来。
具体方法：

分成三组
  因为如果分成四组，若第一次称量一样重之后
  剩下6个球不能分辨，而这时剩下的是9种可能，
  但要担负起对应12种可能的责任，这是不行的。
  同样分成两组也会遇到类似的问题。
abcd  efgh ijkl
先称前两组，如果一样重，简单。

否则，不妨令左边abcd重
那么ijkl就是好球，
左边放abei,右边放cdjh,
再称，如果一样重，坏球可能是fg，
                  称fi，即知
      如果左边重，坏球可能是abh,
                  称ab，即知
      如果右边重，坏球可能是ecd,
                  称cd，即知
这里很重要的一点就是在第二步的时候
一定要打乱两组球的顺序。
因为在第三步的时候它只能由三种称量
结果，为了得到结论，最后的时候要判
断的物体数目一定不可以超过三个。
而如果第二步不打乱分组的话，无论怎
么称量最后都可能至少要判断4个球，这
个应该不难理解。

这个比较有条理,好理解,呵呵

胖子多多

QUOTE:

Originally posted by flywater at 2005-1-2 06:54 PM:
首先考虑有没有可能，称三次，每次
可能的结果是左重，右重，一样重，三种，
那么相当于对应27种可能性，而12个球，
坏球可能重可能轻，则只有24种可能，故
一定可以找出来。

对于你以上的理论依据，我拿不准。在我证明不了这是对的情况下，我想我也只能先把他当做错误的来看了。*.*别人谁有看出名堂来了吗？指点我一下啦

winsen8

宣布个简单的答案

flourish

不敢做，怕受的打击太大！

胖子多多

QUOTE:

Originally posted by flourish at 2005-1-4 10:30 AM:
不敢做，怕受的打击太大！

只不过是一个数学应用题，没什么大不了的。做不做出来，也都证明不了什么。有一种乐趣，就埋在思考的过程当中。

flywater

QUOTE:

Originally posted by 胖子多多 at 2005-1-4 09:20 AM:


对于你以上的理论依据，我拿不准。在我证明不了这是对的情况下，我想我也只能先把他当做错误的来看了。*.*别人谁有看出名堂来了吗？指点我一下啦

可以理解为一个三进制的编码,也就是一个三位的三进制数可以表示27种不同的状态(3的3次方),而把12个球编号,其中一个或轻或重共24种可能,所以理论上可以成功解决这个问题.
如果抛开这个理论,只看过程的话,应该也不难理解.

胖子多多

QUOTE:

Originally posted by flywater at 2005-1-6 10:29 AM:

可以理解为一个三进制的编码,也就是一个三位的三进制数可以表示27种不同的状态(3的3次方),而把12个球编号,其中一个或轻或重共24种可能,所以理论上可以成功解决这个问题.
如果抛开这个理论,只看过程的话,应该也 ...

明白了一些，试了一下13个球，果然也可解得，14个就不行了。
敢问老兄一下，这个理论叫什么名字，一般都可以应用在什么样的问题上？
谢谢啦，我又学了一招~~~

sandflower

QUOTE:

Originally posted by flywater at 2005-1-2 06:54 PM:
一点就是在第二步的时候
一定要打乱两组球的顺序。  ...

理论没学 赞同这一点，直接把判断为一样重量的代以X就更明了