面试题54：找出不同重量的球

12个球和1个天平，已知只有1个和其他的球重量不同，问怎样称才能用3次就找到那个球？（注意此题并未说明那个球的重量是轻是重，所以需要仔细考虑）

答案：首先证明，如果有3个球P1、P2和P3满足，要么P1较重，要么P2、P3中有1个较轻，并且有2个标准球，则质量不同的那个可以用天平一次找出。事实上，取P1，P2与标准球比较，如果平衡则P3为较轻，如果P1、P2质量之和大于标准球则P1为较重的球，如果P1、P2质量之和小于标准球则P2为较轻的球。同理可得，P1、P2、P3满足要么P1较轻，要么P2、P3中有一个较重的情况，同样可以一次找出非标准球。

将球先分成3批（标记为A、B、C组），每批4个，取A、B两批称量。如果平衡，则质量不同的球在C组，可以用两次称量找出（先取两个与标准球作比较，如果平衡再在余下的两个中取1个与标准球作比较，如果不平衡，则在其中取一个与标准球作比较）。如果不平衡（不妨假定C组轻于B组），则C组为标准球。将A,B排列如图21.3所示。

图　21.3　A和B组排列

取A1，A2，B1（A'组）与A3，A4，B4（B'组）分别放在天平两边称量。如果A'组轻于B'组，则要么A1，A2中有较轻的，要么B4为较重的，由前面的证明知，第3次称量可以找出质量不同的那个。如果A'组重于B'组，则要么B1为较重的，要么A3，A4中有较轻的，同样可以找出质量不同的那个。如果平衡，则B2，B3中有较重的，分别放在天平两端即可找出较重的。