两道有趣的题

同事一起去吃饭的路上，喜欢分享一些有趣的题目，最近讨论的两个神题，非常有趣，也非常 难想。

1. 十二个球中找出不一样的那个

12个球，其中只有一个球不一样，该球只是重量跟其他球不一样，但外观是一样的，现在有一 个无砝码的天平，问最少称几次可以找出那个不一样的球？

分析：随便想想，4次称重是很容易找到目标球的，估计没这么简单，估计答案应该是3。答案也确实 是3次，再仔细分析一下，第一次称重必然是分三组，每组4个球，因为只有这样才能最大限度 地剔除一部分球。而且第三次称重，即最后一次称重，必须是对3个球进行，且此时要能够知道 目标球是比其他球重，还是轻。所以关键的第二次称重非常重要，通过这次称重，不仅要剔除到 只剩下3个球，而且还要知道目标球比其他球重还是轻。

答案：第一次称重分三组，球的代号如下，先称左边两组，最坏情况就是1234和5678不等，这样目标 球就在此8个球中。此时不失一般性地假定重量关系为1234 < 5678。

1 2 3 4      5 6 7 8      a b c d

第二次称重，非常巧妙，按如下进行，接下来，我们分析各种可能的结果。

5 2 3 4      1 a b c

如果5234 < 1abc，目标球在234中，而且目标球比其他球轻；如果5234 > 1abc，那么目标球 在5和1中，但不知道目标球和其他球的轻重关系，不过，此时范围已经缩小到2个球的了；如 果5234 = 1abc，那么目标球在678中，而且目标球一定比其他球重。

第三次称重，就很easy了。

2. 情报员如何最快地交换情报

有N个情报员，各自掌握一条情报，任意两个情报员接触一下，那么他们就互相知道了对方所掌 握的情报，此时此两个人掌握的情报条数一样，而且是接触前两个情报的总和。问最少多少次 接触可以使这N个人了解所有的情报，注意一次接触只是两个人之间进行。

分析：估计很快就能想到2N-3次接触是可以搞定的。假如第一个人依次和余下的N-1个人接触，那么此 人就掌握了全部的情报，而且最后接触的那个人也掌握了全部情报。接下来他只需要再跟中间 的N-2个人接触一遍，那么所有人就了解了所有的情报了，所以一共是N-1 + N-2 = 2N-3次。但 答案肯定不是这个，不然就太简单了。

答案：答案是2N-4。问题的突破口在于4个人的时候情况比较特殊，如果按2N-3来算，需要5次，而实 际上只需要4次，想想就能明白。而其他任何人数似乎都没有这个特性。于是乎一种巧妙的解法 诞生了，在N个人中拉4个人出来，让其中一个人与这4个人之外的人都接触一遍，即N-4次，然 后这四个人内部进行4次接触，这样这4个人就了解了所有的情报，然后4个人中的随便一个人再 次与4人之外的所有人接触，又花费了N-4次。总的算起来，就是(N-4) +4 + (N-4) = 2N-4，神 奇吧！