这是一系列的经典面试题,其中最简单的版本是:

有8个硬币,其中一个略重一些,给你一个没有刻度和砝码的天平,最少几次能把重的那个找出来?

这个已经太简单了,现在所有人都知道是2次了。

一个升级版本是:

有8个硬币,其中一个有瑕疵,会略重一些或者轻一些,给你一个没有刻度和砝码的天平,最少几次能把有瑕疵的那个找出来,并且指出到底是重了还是轻了?

这个正常人仔细想一下还是能想出来的,是3次。

如果再升级一下,要求称12个硬币,就比较BT了:

有12个硬币,其中一个有瑕疵,会略重一些或者轻一些,给你一个没有刻度和砝码的天平,最少几次能把有瑕疵的那个找出来,并且指出到底是重了还是轻了?

我们用 表示结果是第X枚硬币较轻,用 表示结果是第X枚硬币较重。则在没有称重的时候,一共有24种可能的结果,一次称重可以得到三种信息,所以我们可以筛掉其中的16种,剩下8种可能的结果。同理,第二次称重时可以再筛掉5种,剩下3种可能的结果。显然,第3次称重就可以确定唯一的结果了。具体称法在http://www.mathsisfun.com/pool_balls_solution.html有。

如果再附加一个条件,该问题可能就非常人所能及了:

称重安排必须是事先确定的,不能边称边调整。即,必须事先确定第一次称重称哪些硬币、第二次称重称哪些硬币、第三次称重称哪些硬币,是否还能称出来?

http://www.careercup.com/question?id=184790有大神给出了一个解,但并没有仔细解释,只能理解为高端大气上档次了。但是仔细想一想,还是能想出构造方法来的。首先把三次称重可能得到的信息一一编码,显然该编码有3位,每一位分别对应一次称重,设左边重编码为L,右边重编码为R,平衡为E,那么有

  • 结果 对应的编码的某一位为L,当且仅当X在该次称重中出现在天平左边;
  • 结果 对应的编码的某一位为R,当且仅当X在该次称重中出现在天平右边;
  • 结果 对应的编码的某一位为E,当且仅当X在该次称重中没有出现。

结果 也有对称的对应关系。有了这个对应关系,很快就可以把三次称重安排出来了。

从上面的讨论可知,3次称重一共可能有27种结果,那么3次称重能否在13枚硬币中找到瑕疵品呢?答案是不可能。
定义对偶编码——若编码A和编码B存在这样的关系,这两个编码互为对偶编码:
对于A的任意一位,

  • 该位为R且B的这一位为L;或
  • 该位为L且B的这一位为R;或
  • 该位为E且B的这一位为E。

27个编码中以R开头的共有9个,其中5个是某5个以L开头的编码的对偶编码,假设这5个编码分别对应结果1L、2L、3L、4L、5L,则有5个以L开头的编码分别对应1R、2R、3R、4R、5R。那么,在第一次称重中硬币1、2、3、4、5在天平的左边,然而只剩下4个以R开头的编码可以对应 ,即天平的右边只能放4个硬币。这样的安排是肯定无效的。 即使边称重边安排也不能解决这个问题,26种可能的结果在第一次称重后只能筛掉16个,剩下10个,第二次称重后剩下4个,而一次称重无法确定唯一结果。