秤球

一個數學問題,指有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球輕。