黄健楸

简体中文

English

简体中文

English

主题

12个球称三次问题完全解析 ​

有 12 个外观相同的小球，其中11个重量相同，有1个重量异常，且不知道该缺陷球是轻是重。现在有一个天平，如何使用这个天平只用3次称重找出这个缺陷球，并且知道是轻还是重呢？

理论求解 ​

12球，可能是轻、也可能是重，一共2×12=24种状态。天平称一次应该是“三进制”操作——天平左右、加上没有上天平的。天平称三次能区分的状态一共是33=27种，显然27>24，也就是只用3次就能完全区分所有球的轻重状态，也就可以找出异常的那一个，并且分清它是偏重还是偏轻。

理论基础是信息论，一般教科书第一章就提到的，所以不要因为自己找不出对应操作，然后就否认能找出了……

第一次称 ​

计算称法 ​

python
x = "放左边的球的数量"
y = "放右边球的数量"
z = "没放在天平的球数"
# 总数
x + y + z = 12
# x、y数量应当一致
x = y
"""
考虑下一步，天平只能称两次了，
也就是区分出 3 * 3 = 9 种状态，
上称的两边，“轻重”情况已知，
故需要除以2
"""
# (x + y) * 2 / 2  <= 3 * 3
x + y <= 9
# z * 2 <= 9
2z <= 9

解得：

x = 4
y = 4
z = 4

也就是：

1234         5678
  |_____?_____|      abcd

若第一次平衡 ​

OOOO         OOOO
  |___________|      abcd(有异常球)

称第二次：

python
x = "放左边的未知球的数量"
y = "放右边球的未知球的数量"
z = "没放在天平的球数"
# 总数
x + y + z >= 4
# 考虑下一步，天平只能称一次了，
# 也就是区分出 3 种状态，上称的两边，
# “轻重”情况已知，故需要除以2
# (x + y) * 2 / 2  <= 3
x + y <= 3
# z * 2 <= 3
2z <= 3

也就是要满足

python
x + y + z >= 4
x + y <= 3
2z <= 3

那就是x + y = 3, z = 1。可是天平两边要平衡，怎么办？补入一个正常球O

ab          cO
|_____?_____|      

OOOO OOO(正常球) d(?)

平衡 ​

ab、cO都是正常球，那么d就是异常球，再用d跟O称一次得轻重。

不平衡 ​

由于对称性，只需要考虑一种即可

python
ab
|			cO
|___________|     

OOOO OOO(正常球) d(?)

计算 ​

python
# 数量不考虑正常球O
x = "换到另一边的球数"
y = "拿走，如有空缺，用正常球替代的球数"
z = "完全不动的球数"

"""
三进制操作，下一次只能区分三种状态，
结果可能在三种操作中的球
TODO: 应该还有别的约束条件
"""
2 * x <= 3
2 * y <= 3
2 * z <= 3
x + y + z = 3

一种解法：

python
x = 1
y = 1
z = 1

可能是，将b球换到右边；把c球拿走；a球不动，再补入一个正常球O：

ab          OO 
|_____?_____|      

OOOO OOd(正常球) c(?)

若第三次不平衡，且维持原先不平衡 ​

ab
|			OO
|___________|      

OOOO OOcd(正常球)

只有a不动，显然a是不正常的球，且重量偏轻

若第三次不平衡，且与原先不平衡相反 ​

			OO
ab		  |	
|___________|     

OOOO OOcd(正常球)

只有b与原来位置相反，b是不正常的球，且重量偏重

若第三次平衡 ​

ab			OO
|___________|      

OOOO OOc (正常球) d

abOO都是正常球，只有d异常

第二次不平衡 ​

由于对称性，另一种情况省略

ab
|			cd
|___________|     

OOOO OOOO(正常球)

若第一次不平衡 ​

1234 
  |          5678
  |___________|      OOOO(正常球)

由于对称性，另一种情况省略

计算 ​

印象里，还要保证天平一边有一个对应操作的

python
# 定义操作
x = "换到另一边的球数"
y = "拿走，如有空缺，用正常球替代的球数"
z = "完全不动的球数"

# 三进制操作，下一次只能区分三种状态，结果可能在三种操作中的球
# 由于轻重状态已知，不需要乘以二
x <= 3
y <= 3
z <= 3
x + y + z = 8

一个解 ​

3个球换到另一边，2个球拿走，3个球啥也不动。确保天平一边每种至少一个

三种后续 ​

  1. 天平平衡，在 x。2个球，一次就能比较出来
  2. 天平保持原状，z 中。3个球，天平一边两个，一边一个。有对称性，假设左边两个，右边一个即可
    1. 右边那个y 拿掉；左边其中一个换到右边（x），右边剩下的不动(z)
      1. 平衡，x
      2. 维持不变，z
      3. 相反，y
  3. 天平相反，在 x 中。3个球，同上
python
1234 
  |          5678
  |___________|      OOOO(正常球)

第二次操作：拿走34，“交换”2、56，1、78不动 ​

天平平衡情况有三：

原状 ​

python
156 
 |          278
 |___________|     
 
 OOOO(正常球)  34(拿走)

之前变动过的球，都不是缺陷球。缺陷球不在被拿走的，也不在被“交换”的，即1、78

python
  1           78
  |_____?______|      
  
  OOOO23456(正常球)

这时“拿走”1、“交换”7、“不动”8，也有三种情况：

原状 ​

之前变动过的球，都不是缺陷球。8就是有问题的球

python
  7 
  |           8
  |___________|			 1（拿走）
平衡 ​

7跟8一样，意味着不是唯一一个缺陷球，缺陷球只能是1

python
  7           8
  |___________| 		 1（拿走）
相反 ​

7跟8不一样，由于缺陷球唯一，缺陷球肯定不是1，剩下的变动改变了缺陷球的位置，也就是被“交换”的7是缺陷球

python
			  8
  7           |
  |___________|		    1（拿走）

平衡 ​

156跟278一样，缺陷球只能在34

python
156  		 278
  |           |
  |___________|  
  
  OOOO(正常球)  34(拿走)

这里注意要用到第一次称重的轻重信息：

1234 
  |          5678
  |___________|      OOOO(正常球)

要么3轻了、要么4轻了。称法很多，比如挑一个正常球O跟3称。

相反 ​

156跟278重量不一，由于缺陷球唯一，缺陷球肯定不在34，剩下的变动改变了缺陷球的位置，也就是缺陷球在被“交换”的256。解法跟维持原状类似

python
    		 278
 156          |
  |___________|  
  
  OOOO(正常球)  34(拿走)

版权所有 © 2024-2025 黄健楸