三进位制与称球问题

我们先来描述一下这道经典的趣味数学问题：

有12个外表相同的球，其中有1个坏球，它的重量和其他11一个有轻微的（但是可以测量出来的）差别。现在有一架没有砝码的很灵敏的天平，问如何称三次就保证找出那个坏球，并知道它比标准球重（轻也同理）。

现在我们把问题先搁置在一边，尝试做一些基础的工作。

先从3个球开始。把其中的2个球放在天平上，（1）如果天平平衡，则未放进天平中的1球为坏球；（2）如果天平不平衡，坏球必定在天平重的一端。因此，称量1次就可以找到那个环球。

把球增加到9个。把9个球分成3堆，每堆3个球。把其中2堆放在天平上，（1）如果天平平衡，则未放进天平中的1堆3个球中必有1坏球；（2）如果天平不平衡，坏球必定在天平重的一端的3个球中。对有坏球的3个球中按照上述步骤称量1次，就可找出那个环球因此，称量2次就可以找到那个环球。

继续把球增加到27个。把27个球分成3堆，每堆9个。把其中2堆放在天平上，（1）如果天平平衡，则未放进天平中的1堆9个球中必有1坏球；（2）如果天平不平衡，坏球必定在天平重的一端的9个球中。按照上面步骤，可以找到球球。因此，称量3次就可以找到坏球。

以此类推，可以得出结论：球的个数为N（其中1个为坏球），转化为三进制

N=（100…0）₃，假定出现了m个0,0的个数m就是需要称量的次数m。

例如，81=（10000）₃，表示如果在81个球中有一个坏球，称量4次即可找到那个坏球

729=（1000000）₃，表示在729个球中有一个坏球，称量6次即可找到那个坏球。

上面讲述的是球的个数刚好是3的整数m次方的情形。如果球的个数不是如此，又该如何呢？正如一开始就出现的问题那样，是12个球的情形。

我们先来看4个球的情形。把4个球分成1球、1球、1球和1球共4堆，则2次称量可找到坏球。再来看8个球的情形，可以分成 3球、3球、2球共3堆，则称量2次也可找到坏球。

对于12个球的情形可以同样完成，可以把12个球9球、3球共2堆。按照上面描述的办法，称量3个就可以找到坏球。

以此类推，我们的结论是：

球的个数为N（其中1个为坏球），转化为三进制

（100…0）₃（m+1个0）<=（100…0）₃（m个0），

m+1就是需要称量的次数。

也就是说，从27个球找出1个坏球与从10～26个球中找出1个坏球，所需要的称量次数是完全一样的，都只需要3次。

我们把任意一个正数N改写成三进制的数相加，就可以找到整个称量的过程。

26=（100）₃+（100）₃+（10）₃+（10）₃+（1）₃+（1）₃

例如，要在26个球中找出其中的1个坏球，只要把26分成9球、9球、3球、3球、1球、1球这样的6堆，只要称量3次就可以了。

第一次，9个球放在天平两端，如天平不平衡，坏球必在某一端的9个球之中，重复上述步骤可找到。如天平平衡；则把未放在天平的3个球、3个球放在天平上。如天平还不平衡，则把1个球、1个球放在天平上，则必定不平衡，坏球找到。

好了，我想类似问题的解决应该是很轻松的。例如，100枚硬币中有1枚重于其他99个标准硬币的坏硬币。如何用没有砝码的天平，以最少的次数找到这枚坏硬币。