导读: 12个外表一样的小球 其中11个球重量相同 1个球为[异常球] 可能重量比较重也可能比较轻 如何利用天平称重3次来找出这个[异常球]?
本文作者为 简书-melo的微博 / 掘金-melo的微博 / Github-meloalright
转载请注明出处哦。
0.了解历史沿革
称球问题是一个经典的数学问题
理论上称球问题只要球的数量小于等于 (3^n − 3)/2 就一定可解
维基百科的解释如下:
称球问题 是指若在最多 (3^n − 3)/2 个球中有一个特殊球的重量与众不同（不知道偏重还是偏轻）
而其他球的重量全部相同 则用无砝码的天平称n次可以找出特殊球 并确定特殊球是偏轻还是偏重
如果有 (3^n − 1)/2 个球 则同样可以保证找出特殊球 但不一定能确定特殊球是偏轻还是偏重
1.第一次称重
1.分三组 {A1, A2, A3, A4} {A5, A6, A7, A8} {A9, A10, A11, A12}
2.前两组称重 {A1, A2, A3, A4} --- {A5, A6, A7, A8}
情况1: 左边重
(ps:证明[异常球]在前两组8个球里 可能是第一组有球异常重-或者第二组有球异常轻)
情况2: 右边重
(ps:证明[异常球]在前两组8个球里 可能是第一组有球异常轻-或者第二组有球异常重)
情况3: 平衡
(ps:证明[异常球]在第三组4个球里)
ps:如果[平衡]那就好说了 证明[异常球]在第三组的四个球{A9, A10, A11, A12}里 这种情况我们稍后再做分析
ps:下面先介绍未平衡的复杂情况 以[情况1左边重]举例
2.第二次称重
0.声明: {A9, A10, A11, A12}都是[无辜球] 因为第一步已经确认[异常球]在前两组
1.为前两组引入1个[无辜球]来分组 {A1, A2, A3, A4, A5, A6, A7, A8, 无辜} 现在有9个球
2.再把9个球再分三组
# 这里分组方法比较复杂
>>> 这次3组的分组方式首先为
'''
{A1, A2, A3} {A5, A6, 无辜} -----
/ | \ / | \
{A1, A2, A3, A4, A5, A6, A7, A8, 无辜}
\ | /
--------{A4, A7, A8}
'''
>>> 我们看到[原先的第一组]去掉了{A4} [原先的第二组]去掉了{A7}{A8}
>>> 去掉的这3个球组成了第三组{A4, A7, A8}
>>> 第二组则补上了一个[无辜球]
>>> 目前得到的3个分组为
>>> {A1, A2, A3}
>>> {A5, A6, 无辜}
>>> {A4, A7, A8}
>>> 然后再让前两组的{A2}和{A6}互相交换
>>> 我们称之为[叛变球]
'''
{A1, A2, A3}
^|
|v
{A5, A6, 无辜}
'''
>>> 最终的3个分组为
>>> {A1, A6, A3}
>>> {A5, A2, 无辜}
>>> {A4, A7, A8}
3.把前两组称重 {A1, A6, A3} --- {A5, A2, 无辜}
情况1: 发生反转 右边重
(ps:证明[异常球]还在前两组中 而且就在[叛变球]-{A2}和{A6}中)
情况2: 还是 左边重
(ps:证明[异常球]还在前两组中 而且在这两次称重都没动位置的{A1}{A3}{A5}中)
情况3: 平衡
(ps:证明[异常球]在第三组{A4, A7, A8}中)
ps:如果是[发生反转]那就好说了 证明异常球在[叛变球]-{A2}和{A6}中 这种情况我们稍后再做分析
ps:如果是[左边重] 证明了相比[第一次称重结果] 去掉{A4, A7, A8}和叛变{A2}与{A6}都不能改变左边重的这个结果 所以异常球一定在这两次称重都没动位置的{A1}{A3}{A5}中 一定是{A1}{A3}其中一个异常重-或者{A5}异常轻
ps:[左边重]和[平衡]的接下来处理方案其实是思路一样的 我们以[情况2左边重]为举例继续
3.第三次称重
0.声明:异常球一定在{A1}{A3}{A5}中 一定是{A1}{A3}其中一个异常重-或者{A5}异常轻
1.直接{A1}和{A3}互相称重一下
情况1: {A1}重
(ps:答案已找到 => {A1}是异常球 重量异常重)
情况2: {A3}重
(ps:答案已找到 => {A3}是异常球 重量异常重)
情况3: 平衡
(ps:答案已找到 => {A5}是异常球 重量异常轻)
ps:答案已找到
4.其他情况同理
2.2-本文在[第一次称重]未详细分析的[情况2右边重]情况同样可以以同一思路解决
2.3-本文在[第一次称重]未详细分析的[情况3平衡]情况 可得知[异常球]在{A9, A10, A11, A12}当中 可以在[第二次称重]将{A9, A10}与{A11, 无辜}互相称重 若[平衡]就好说了 直接得知[异常球]是{A12} 若[左边重]则可能{A9, A10}存在[异常球]且异常重-或{A11}为异常球且异常轻 接下来[第三次称重]以上文同一思路解决即可
3.1-本文在[第二次称重]未详细分析的[情况1发生反转]情况 可得知[异常球]在{A2}或{A6}当中 可得知可能{A2}为异常球且异常重-或者{A6}为[异常球]且异常轻 接下来[第三次称重]直接取任意[无辜球]与{A2}称重即可得知答案
3.3-本文在[第二次称重]未详细分析的[情况3平衡]情况 可得知{A4, A7, A8}为[异常球] 并对比[第二次称重]结果可知 可能{A4}为[异常球]且异常重-或{A7}{A8}存在[异常球]且异常轻 接下来[第三次称重]以上文同一思路解决即可
5.题外话
关于这道题的可解性: 有一个信息熵的解释大家可以看下
其中12个球找到异常球的信息熵是 log(12)
找到异常球后得知轻重信息的信息熵是 log(2)
所以问题的总信息熵是 log(12) * log(2) = log(24)
每次称重包含左-右-平衡三种情况 所以每次称重的信息熵是 log(3)
3次称重的总信息熵是 log(3) * 3 = log(27)
因为: log(27) > log(24)
所以: 3次称重内一定可解
结语:
本文的12球称重问题就分析到这里啦
(∩_∩)求点赞求关注哦
网友评论