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