磨剑(4)与众不同的乒乓球

tags: iq

——————— 好几年前写的东西了,朝花夕拾,略有删改。

问题

有十二个乒乓球形状、大小相同,其中只有一个重量与其它十一个不同,现在要求用一部没有砝码的天秤称三次,将那个重量异常的球找出来,并且知道它比其它十一个球较重还是较轻。

解法

首先,将12个球编号,ABCDEFGHIJKL,每四个一组,分三组。
第一次,ABCD与EFGH先上天平,
如果ABCD=EFGH,说明IJKL里存在特殊球,ABCDEFGH都是标准球,我们把标准球标为X。
如果I+X=J+K,说明L一定是特殊球。L与IJK中任何一个比,就能得出是重是轻。两次内搞定。
如果I+X>J+K,说明L是正常球,特殊球可能是重了的I,也可能是轻了的J和K。
第三次用I+J与X+X比,
如果相等,说明IJ都是正常球,K才是特殊球,经合前面的I+X>J+K,可知道,K轻。
如果I+J>X+X,说明I一定是特殊球,并且过重。
如果I+J 如果I+XJ+K相通。
如果ABCD≠EFGH,说明ABCDEFGH里存在一个特殊球。IJKL都是标准球。我们还有两次机会,引入标准球X帮忙。
假设ABCD>EFGH,第二次,比较AE和BC。
若AE=BC,说明ABCE都是标准球,说明要么D过重,要么FGH中一个过轻。第三次比较DF与GX,
若DF=GX,说明F或H过轻。比一次就知道。
若DF>GX,说明G过轻或者D过重,比一次就清楚。
若DF 若AE>BC,很明显,A过重。不用再比。
若AE 若BE=XX,说明C过重。
若BE>XX,说明B过重。
若BE 假设ABCDEFGH相通。
搞定!

分析

这个题在网上传得很广。可惜绝大部分答案都是错的。
我最近一次在网上看到,是ChinaUnix上论坛上的一个帖子。太多自以为是的人,连题都没看清就说答案了。一些人甚至的十分幼稚和专横——错就错了,还不承认,拿一副资深牛逼人士的面孔来搪塞……
大学有次看到这题,第一反应也错了,那天晚上想了很久才找到办法。个人感觉这题挺折磨人的。
第一个难点在于,那个与众不同的球是轻了还是重了,我们并不知道。如果知道它是重还是轻,很简单的2分法就可以三次搞定。人只要不傻,都能十分钟解决。99%的错误答案都没认真考虑这个限制。这也是容易误导思考的地方。
第二个难点在于,二分查找的思维定势限制了思路。读懂了题意却没解出来的人,大都栽在这里。
这道题的关键有两个,一是要给球编号,二是要好好利用标准球。
我最初也用2分法尝试,当然碰壁了,多思考一下就可看出,这个方向不对。我第一次失败就在这儿,然后就没有深入了。
后来认真反省了一下,决定从最简单的情况入手。先分析一下,什么条件下,我们才能定位特殊球。
  • 2个球中有1个特殊球,明显地,除非我们知道它是重是轻,不然没法找出来。这是难倒大部分人的根本原因。他们的解决方案最终总是走到了这一步。
  • 3个球的时候,即使不知道特殊球是轻是重,我们能在2次内找到特殊球。
    ABC三球,先用AB放天平两端,如果平衡,说明C球有问题,将AB中任何一个与C再在天平上称一次,C轻还是重立即可知。如果AB不平衡,记住是哪边重。假设A重,然后用C球与A球比较,如果平衡,则B是特殊球,偏轻。如果不平衡,肯定A就是特殊球,偏重。
    如果我们知道特殊球是轻是重,我们只需要一次!
    注意,这里有一个方法很关键,在比较的过程中,逐渐标出标准球!
  • 4个球的时候需要几次?
    首先2分法会遇到情况①,至少需要3次才能保证找到。这不是我们想要的。
    换个思路,假设这4个球为ABCD,第一次拿AB上天平比,
    如果A≠B,说明AB中某个有问题,CD是标准球。假设A重些B轻些,拿A与C比,如果A还重,那A就是特殊球,轻重。否则,B就是特殊球,较轻。这样,只需要再一次的比较,挺好。
    如果A=B,麻烦了,CD依旧陷入了①的情况,需AB做标准球参考,因此仍需要两次。
    这个思路也行不通。
    4个球的情况是很简单的,多尝试一下,可以得出结论:不可能2次内在4个球中找出特殊球,同时确定其过轻还是过重。
这个结论很令人沮丧,这也是我为什么质疑朋友的题目记错了……
所以,我简单的认为,4个球都需要3次,那12个球应该会要更多次。至少要花一次把范围缩小吧?

当时对自己的猜测过于自信了……就没有在继续研究下去。
那天晚上,我忽然想到一点。额外的球其实会提供一个额外的信息——标准球。标准球的参与,可以化解很多未决状态!使得4个球加一个标准球,能在两次内完成任务。

假设ABCD中有一个特殊球,而X是一个标准球,A+X与B+C比,
  • 如果A+X=B+C,说明D一定是特殊球。D与ABC中任何一个比,就能得出是重是轻。
  • 如果A+X>B+C,说明D是正常球,特殊球可能是重了的A,也可能是轻了的B和C。
    再用A+B与X+X比,
    • 如果A+B=X+X,说明AB都是正常球,C才是特殊球,经合前面的A+X>B+C,可知道,C轻。
    • 如果A+B>X+X,说明A一定是特殊球,并且过重。
    • 如果A+B<X+X,说明B一定是特殊球,并且过轻。
  • 如果A+X再用A+B与X+X比,
    • 如果相等,说明AB都是正常球,C才是特殊球,经合前面的A+X>B+C,可知道,C重。
    • 如果A+B>X+X,说明B一定是特殊球,并且过重。
    • 如果A+B<X+X,说明A一定是特殊球,并且过轻。
以上可以看出,四个球可以两次完成。想通这里,答案就清晰了。