1. 问题
有 12 个 外观完全一样的小球,其中有 1 个求的重量和其它 11 个球不一样(或称为坏球),但是不知道是轻还是重。现在你有一架天平,只能称 3 次。你怎么找出这 12 个球中重量不同的那 1 个球,并指出这个球是轻还是重?2. 分析
破解问题前提:
(1) 解决问题的基础是充分理解问题;
(2) 要在可能性的边界之内做事,才会有成效;
(3) 消除不确定性的根本在于获得信息;
(4) 要学会科学的试错方法。
1) 读懂问题
这个问题中隐含三点重要的信息:
(1) 这个问题不是说有 11 个好球和 1 个坏球,而是 12 个球每个球都有可能是好球或者坏球,在最终确定答案之前,每个球都可能有问题。
(2) 这个问题的本质其实是 24 选 1。
24,就是指12个球,每个球2种可能性,一共24种可能性。分别是:第1个球轻,或者第2个球轻,……,直到第12个球轻,这是前12种;同样的,还有另外12种,第1个球重,或者第2个球重,……,直到第12个球重。我们将这些可能性简写成1轻,2轻,……,12轻;1重,2重,……,12重。
最终我们要找到哪个球是坏球,它是轻是重,这个问题就变成了:有 24 种可能性,我们如何排除掉其中的 23种,最终留下 1 种。
(3) 关键信息是关于天平,有人想到天平,就觉得它只能告诉我们哪边轻哪边重。但实际上用天平称重,每一次可能会产生三种结果:左边轻,左边重,或者两边相等。要注意两边相等也是一条信息。
一次天平称量能够产生的信息量就是一个三进制数位,英文里叫1吹特(trit),可以对应于二进制的1比特(bit)。我们这里分别用 “<”、“>” 和 “=” 这三个符号来表示这三种结果。
把这三层意思读出来,才算是读懂了这道题给出的条件,读懂了题目,解题就不难了。
2) 确定边界和消除不确定性
这道 12 球问题的边界在哪里?
要消除不确定性,所需要的东西就是信息。这个问题实际上是 24 选 1;又知道了每一次用天平称量,最多能得到 1 吹特的信息,称三次最多就能得到3位三进制的信息。
3 位三进制,对应的就是 3x3x3=27 种可能性,题目要求我们分辨的是 24 种可能性,27 > 24,所以这道题是可能有解的。这就是确认了在边界内做事。
接下来要留意,如果某一步之后超出了边界,那后面的路就不可能走通了。这一点是解题的关键,也是指导我们往下解题的准则。在我们的解题方案中,每称一次必须获得一个三进制的信息,否则这个问题是解决不了的。
这里可以看一个经典的错误做法:很多同学第一次称球是把 1-6 放在天平左边,7-12 放在右边。但这样做结果只可能是左边重或者右边重,不可能出现两边平衡的情况,因为有一个坏球存在,那么我们只能得到一个二进制信息。不论左边重还是右边重,可能性都是从 24 种变成了 12 种。如果 1-6 这边轻,那么可能性就是 1轻、2轻、……、6轻,或者7重、8重、 ……、12重,一共12种可能性。反过来也是一样。
而此时只剩下 2 次称量机会,最多只能得到 3x3=9 种可能性,9 < 12 种,这就是越过了边界,是不可能成功的。
3. 解题
怎么运用科学试错方法?
现在我们有了理论的指导,知道了每次称量都必须要获得一个三进制的信息。
1) 第一步
我们将 12 个球分为三组,1-4,5-8 和 9-12 各一组,然后把前两组放到天平两侧上去称量。这样我们就有可能得到 <、= 或者 > 三种情况,这三种情况不论是哪一种,在各自的结果下都只剩下 8 种可能性要排除。逻辑图如下:
我们可以把这三种情况下各自的 8 种可能性列举出来:
(1) 如果是左边轻,就剩下 1轻~4轻,5重~8重这 8 种可能性;
(2) 如果平衡,就剩下 9轻~12轻,9重~12重这 8 种可能性;
(3) 如果是左边重,就剩下 1重~4重,5轻~8轻这 8 种可能性;
这一步走对了,接下来就会减少很多不必要的试错。
2) 第二步
我们分别来处理这三种可能性。
(1) 天平平衡,即 “=” 的情况
先说简单的一种,“=” 的情况,也就是天平两边相等,那我们就知道了,1-8球都是好球,坏球一定在9-12号这四个球当中,每个球有轻重两种可能性,一共就是8种。
我们就要继续把8种可能性缩小。如果不知道我们前面的理论,很有可能出现的一种错误做法就是把9-12四个球平分成两组来称,但这样称的结果一定是一边高一边低,又是只有二进制的信息,显然是错误的道路。
正确的做法是什么呢?
把8种可能的情况列举出来:有9轻~12轻,9重~12重。然后利用“三进制”信息能将可能的情况除以3的特点,将8种情况分为三组,分别是3种、3种、2种。
另外我们这时还有一个可以利用的信息,就是经过第一次称量我们已经知道了1-8号球都是好的。因此第二次称重时,可以利用这些好球,把1-3三个好球放在天平的一边,把可能是坏球的9-11放在天平的另一边去称。
称的结果有三种:9-11轻,9-11重和平衡。
如果平衡,就说明9-11都是好球,坏球就是12,但还有12轻和12重2种可能性,拿12和任意一个好球再称一次就能得出答案了。
如果不平衡,是9-11轻或者9-11重,各自就再对应3种可能性。比如9-11轻,剩下的可能性就是9轻、10轻、11轻,把9和10再称一下,如果平衡,就是11轻;如果不平衡,哪边轻哪边就是坏球。9-11重也是同理。
(2) 天平平衡,即 “>” 或 "<" 的情况
我们以左边这一组轻来说明,如果是左边重,方法也是对称的。
如果左边轻意味着什么?意味着有8种可能性:要么是坏球在1-4这边,坏球是一个轻球,对应1轻-4轻4种情况;要么是坏球在5-8那边,是一个重球,对应5重-8重4种情况。一共8种。
接下来这一步很关键,我们必须通过称一次,把8种可能性变成3-3-2三组。如果达不到这个目的就是盲目试错。这一步具体的做法有好几种,道理上大同小异,我讲其中的一种。下面这段分析我推荐你对着文稿中的逻辑图来听。
怎样把1轻-4轻、5重-8重这8种情况分成3、3、2呢?
一个办法是,将1、2这两个可能的轻球,加上确定是好球的9放在天平的左边,把3、4两个可能的轻球,加上可能的重球5放在天平的右边进行称量。
这次称量之后,有A,B,C三种情况,我们对照逻辑图来看:
情况A:1、2、9这边轻,说明可能的情况是1轻、2轻和5重,这三种情况可以再称一次就确认最终答案。
情况B:1、2、9和3、4、5平衡了,说明可能的情况是6重、7重、8重,接下来也是再称一次就可以得到答案。
情况C:1、2、9这边重,说明1、2都不是轻球,同时天平右边的5也一定不是重球,只能是天平右边的3和4当中有一个是轻球,导致了1、2、9会比3、4、5重。那么再称一次,找到究竟是3轻还是4轻,就得到了最终答案。
总之,只要在第二次称的时候,能够把8种可能性再分成3+3+2种可能性,接下来再称一次问题就肯定解决了。因为最多也无非是3种可能性,称1次必然会得到结果。
在这个过程中,恪守一个原则,就是每称一次,就把可能的情况除以了 3,否则下一步就会完成不了任务。而这个原则,是靠前面的确定边界和用信息消除不确定性的方法得到的。凭借一个合理、合逻辑的思路往前走,这就是科学试错的方法。
4. 总结
读懂题目、确定边界、用信息消除不确定性、科学试错,这些具体的方法共同构成了一个系统性的方法论,这就提醒了我们系统性学习的重要性。
作为一个普通人,我们在面对未知的难题时,只有对自己运用的方法有系统性的了解,对自己的方法有清晰的理解和把握,才有可能解决这个未知的难题。如果对题目也不了解,对自己使用的方法也不了解,那就是盲目行事,即使能碰运气碰出结果,效率也非常低。