秤球問題

一個數學問題,指有n個相同質量的產品中有混入1個瑕疵品,且該瑕疵品的質量不同,試問要如何用無砝碼的天平在有限次數內找出該瑕疵品

称球问题,是指若在最多3n − 3/2个球中有一个特殊球的重量与众不同(不知道偏重还是偏轻),而其他球的重量全部相同,则用无砝码的天平称n次可以找出特殊球,并确定特殊球是偏轻还是偏重; 如果有3n − 1/2个球,则同样可以保证找出特殊球,但不一定能确定特殊球是偏轻还是偏重。(n ≥ 2)

10個硬幣中找出伪幣的解題動畫。這例子中伪幣的重量比其他硬幣輕。

以下主要介绍最简单的12个球称3次的版本。

动态称法

动态调整称球方案是最常见的处理手法,在各种答案中,下表所列是其中的一种表述:

第一次称球情况 第二次称球情况 第三次称球情况 结论
首先
左1、2、3、4
右5、6、7、8
若左重 其次
左1、5、9:右2、3、6
若左重 最后
左4:右1
若平衡 则6轻
若右重 则1重
若平衡 最后
左4、8:右1、2
若左重 则4重
若平衡 则7轻
若右重 则8轻
若右重 最后
左4、8:右2、5
若左重 则5轻
若平衡 则3重
若右重 则2重
若平衡 其次
左9、11:右2、10
若左重 最后
左9、10:右1、2
若左重 则9重
若平衡 则11重
若右重 则10轻
若平衡 最后
左4:右12
若左重 则12轻
若右重 则12重
若右重 最后
左9、10:右1、2
若左重 则10重
若平衡 则11轻
若右重 则9轻
若右重 其次
左1、5、9:右2、3、6
若左重 最后
左8、9:右2、5
若左重 则2轻
若平衡 则3轻
若右重 则5重
若平衡 最后
左4、8:右1、2
若左重 则8重
若平衡 则7重
若右重 则4轻
若右重 最后
左4:右1
若左重 则1轻
若平衡 则6重

最后给出的结论,判断依据与下述的固定称法的解释完全一致。

固定称法

固定称法方案如下:

  • 第一次称:左盘放置1、2、3、4号球, 右盘放置5、6、7、8号球
  • 第二次称:左盘放置1、5、9、11号球,右盘放置2、3、6、10号球
  • 第三次称:左盘放置4、8、9、10号球,右盘放置1、2、5、12号球

按此方案称球,根据天平的状态,可辨别出问题球。判断如下:

  • 若左重、左重、右重,判定是1号球重;若左轻、左轻、右轻,判定是1号球轻;
  • 若左重、右重、右重,判定是2号球重;若左轻、右轻、右轻,判定是2号球轻;
  • 若左重、右重、平衡,判定是3号球重;若左轻、右轻、平衡,判定是3号球轻;
  • 若左重、平衡、左重,判定是4号球重;若左轻、平衡、左轻,判定是4号球轻;
  • 若右重、左重、右重,判定是5号球重;若右轻、左轻、右轻,判定是5号球轻;
  • 若右重、右重、平衡,判定是6号球重;若右轻、右轻、平衡,判定是6号球轻;
  • 若右重、平衡、平衡,判定是7号球重;若右轻、平衡、平衡,判定是7号球轻;
  • 若右重、平衡、左重,判定是8号球重;若右轻、平衡、左轻,判定是8号球轻;
  • 若平衡、左重、左重,判定是9号球重;若平衡、左轻、左轻,判定是9号球轻;
  • 若平衡、右重、左重,判定是10号球重;若平衡、右轻、左轻,判定是10号球轻;
  • 若平衡、左重、平衡,判定是11号球重;若平衡、左轻、平衡,判定是11号球轻;
  • 若平衡、平衡、右重,判定是12号球重;若平衡、平衡、右轻,判定是12号球轻。

在此說明第一種情況(左重、左重、右重)的判斷方法:

  • 第一次左重,划掉9、10、11、12,剩下1、2、3、4、5、6、7、8可疑
  • 第二次左重,划掉4、7、8,剩下1、2、3、5、6可疑
  • 第一、二次均左重,划掉2、3、5,剩下1、6可疑
  • 第三次右重,划掉6,仅剩1,可判定重。

同理,若左轻、左轻、右轻,判定是1号球轻。其餘依此類推。,

数学方法

固定称球方法,可以采用数学方程式来表达: ,其中:    

矩阵方程是用天平称球的情况描述,即:左盘总重量—右盘总重量=差值,下面进一步解释A、X、Y的含义及判定规则。

首先:因为在12个球中,只有1个球与其它球重量不一样,所以在逻辑上使用±1来代表重量差±△X。

其次:A为3行12列矩阵,系数矩阵的第i行第j列元素表示第i次第j号球的位置。1代表小球被放在左盘,-1代表小球被放在右盘,0代表小球不参与称重。

  • X为12行1列矩阵,表示12个球的重量;
  • Y为3行1列矩阵,表示3次称球的结果。左盘比右盘重时,用1表示;左右盘平衡时,用0表示;左盘比右盘轻时,用-1表示。

最后:当Y与A的第j列相等时,则判定为第j球重;当Y与A的第j列的负向量相等时,则判定为第j球轻。