秤球
一個數學問題,指有n個相同質量的產品中有混入1個瑕疵品,且該瑕疵品的質量不同,試問要如何用無砝碼的天平在有限次數內找出該瑕疵品
此條目沒有列出任何參考或來源。 (2010年2月11日) |
稱球問題,是指若在最多3n − 3/2個球中有一個特殊球的重量與眾不同(不知道偏重還是偏輕),而其他球的重量全部相同,則用無砝碼的天平稱n次可以找出特殊球,並確定特殊球是偏輕還是偏重; 如果有3n − 1/2個球,則同樣可以保證找出特殊球,但不一定能確定特殊球是偏輕還是偏重。(n ≥ 2)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/82/False_Coin_Problem.gif/400px-False_Coin_Problem.gif)
以下主要介紹最簡單的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球輕。