磨剑（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个球应该会要更多次。至少要花一次把范围缩小吧？

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

假设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一定是特殊球，并且过轻。
以上可以看出，四个球可以两次完成。想通这里，答案就清晰了。