|||
1月30日,科学网的应行仁老师发表博文《称球问题》,提出智力思考堆栈(Call Stack)的深度概念,获编辑部青睐,精选置顶。一时间科学网众博主兴趣多多,到目前为止共有23位博主推荐,50个评论,3592人次访问。
称球问题的源头还是科普才女,张天蓉老师的杰作:有十三个球,其中十二个重量相同,只有一个次品,不知是轻了还是重了。请用天平秤三次,将这个次品找出来。本来应老师已给出基本的称法,大家深入理解就是了,但不想有两位较真的博主硬是要从命题本身来否定这个练脑小题。
数学行家李世春老师看到后,以极大的兴趣另发博文《8个球就可以证明“十三球问题”(称球问题)无解》,特别作出结论:无论怎么摆放球,称量3次不可能从13个球中找到那个次品。
物理学家戴德昌老师也专门撰文,认为此问题需要穷举法和运气来解决,调侃道《称球问题是忽悠小朋友》,认为“哥哥”,的问题错了。
本文给出高中生Danilo Li (柱柱) 和巴西利亚大学博士生郑建亚对称球问题的的两种解法。Danilo Li的方法共列出20种可能通过3次秤球找到次品。郑建亚的的解法,共有13种可能称法找到次品。列出两种算法的目的在于说明称球问题应该有解,而且还有多种方法。
本文应着张天蓉老师的初衷,让孩子和学生们练练脑。文中的表述仅以秤3次过程中相关的逻辑关系,找出次品为目的,没有任何完备性理论证明和数学模式化。期待着应行仁老师下一篇文章对此问题的构造性证明和新的提示。敬请应行仁老师、李世春老师和戴德昌老师等科学网的众博友指导访问。
一、Danilo Li的解法
1. 四四分法的平衡情况
第一次秤:
A(4)球―――――――――――――B(4)球
△
上图中A表示天平的左边,B表示天平的右边。括号内的数字表示天平该边托盘上放置的球的数目。
1.0: 两边平衡
在A 边保留3个球
从剩余的5个球里面拿出3个放B边。
平衡情况
第二次秤:
A(3)球―――――――――――――B(3)球
△
可分为两种情况:
1.1: 两边平衡
在A边保留1个球,从剩余的2个球里面拿出1个放B边。
第三次秤:
A(1)球―――――――――――――B(1)球
△
1.1.1: 两边平衡
从剩余的1个球是次品。(第1种可能)
1.1.2: 两边不平衡
B 边的球是次品。(第2种可能)
1.2: 两边不平衡
B 边的3个有次品
1.2.1 B 边朝下,说明次品更重
B 保留1个,从B边拿下的两个球任意一个放到A边
第三次秤:
A(1)球―――――――――――――B(1)球
△
三种情况:
1.2.1.1 A边朝下,则是 A边这个球是次品;(第3种可能)
1.2.1.2 B边朝下,则是 B边这个球是次品;(第4种可能)
1.2.1.3 两边平衡, 则是原B边第3个球是次品。(第5种可能)
2. 四四分法的不平衡情况
由于该情况较复杂,下面在称球的过程中,加上各球的编号,分别放在天平两边托盘上面。
第一次秤:
1,2,3,4 5,6,7,8
A(4)球―――――――――――――B(4)球
△
剩下5个球:9,10,11,12,13
不平衡情况 - A边朝下,B边朝上
情况 2.0: 两边不平衡
因为第一次秤时的不平衡,次品应在1,2,3,4 号球或5,6,7,8 号球中。
第二次秤:
1,2,5,6,7 9,10,11,12,13
A(5)球―――――――――――――B(5)球
△
将B边 3个球:5,6,7号球放到A边。把原A边的球里拿出2个:3,4号球。
2.1 两边平衡
因为平衡,已知次品球在3,4,或8号球中。
第三次秤:
3,8 9,10
A(2)球―――――――――――――B(2)球
△
2.1.1 两边平衡
根据第二次秤时的平衡结果,在此情况下只有4号球是次品。(第6种可能)
2.1.2 两边不平衡
在此情况下3或8号球会是次品。
2.1.2.1 A边朝下
如果第一次秤,A边朝下, 3号球是次品。(第7种可能)
如果第一次秤,B边朝下, 8号球是次品。(第8种可能)
2.1.2.2 A边朝上
如果第一次秤,A边朝下, 8号球是次品。(第9种可能)
如果第一次秤,B边朝下, 3号球是次品。(第10种可能)
2.2 两边不平衡
因为不平衡,已知次品球在1,2,5,6或7号球之中。
2.2.1 第一次秤A边朝下且第二次秤A边还是朝下
1或2号球会是次品。
第三次秤:
1 2
A(1)球―――――――――――――B(1)球
△
2.2.1.1 A边朝下
1号球是次品。(第11种可能)
2.2.1.2 B边朝下
2号球是次品。(第12种可能)
2.2.2 第一次秤A边朝下且第二次秤A边朝上
5,6或7号球是次品。
第三次秤:
5 6
A(1)球―――――――――――――B(1)球
△
2.2.2.1 A边朝下
6号球是次品。(第13种可能)
2.2.2.2 B边朝下
5号球是次品。(第14种可能)
2.2.2.3 两边平衡
7号球是次品。(第15种可能)
2.2.3 第一次秤A边朝上且第二次秤A边朝下
5,6或7号球是次品。
第三次秤:
5 6
A(1)球―――――――――――――B(1)球
△
2.2.3.1 A边朝下
5号球是次品。(第16种可能)
2.2.3.2 B边朝下
6号球是次品。(第17种可能)
2.2.3.3 两边平衡
7号球是次品。(第18种可能)
2.2.4 第一次秤A边朝上且第二次秤A边还是朝上
第三次秤:
1 2
A(1)球―――――――――――――B(1)球
△
2.2.4.1 A边朝下
2号球是次品。(第19种可能)
2.2.4.2 B边朝下
1号球是次品。(第20种可能)
二、郑建亚的解法
该算法也是基于四四分法,将13个球分别进行编号,1-13号。?为标准球。
第一步 (1,2,3,4) VS (5,6,7,8)
共有两种情况:平衡1.1和不平衡1.2
1.1 天平平衡,说明问题在(9,10,11,12,13),其他球为标准球。
第二步(9,10,11) VS (?,?,?)
同样有两种情况:平衡1.1.1和不平衡1.1.2
1.1.1 平衡说明问题在(12,13)球。
第三步:(12) VS (?)
得到结果:如果平衡,13号是次球。
如果不平衡,12是次球。
1.1.2 不平衡说明问题在(9,10,11)球,而且知道次球比标准球是轻还是重。
第三步:(9) VS (10)
得到结果:如果平衡,11号是次球。
如果不平衡,根据次球的轻重可以确定10或9哪个是次球。
1.2 天平不平衡,说明问题在(1,2,3,4,5,6,7,8)球。
同时可知重量(1+2+3+4 >或< 5+6+7+8)
第二步 (1,2,3,5)VS (4,?,?,?)
有两种情况:1.2.1 平衡和1.2.2 不平衡。
1.2.1 平衡说明问题在(6,7,8)球。而且可以确定次球轻重。
第三步 (6)VS(7)
得到结果:如果平衡,8号是次球。
如果不平衡,根据次球轻重可知7或6号是次球。
1.2.2 如果不平衡说明问题在(1,2,3,4,5)球。
不平衡有两种情况,1.2.2.1天平倾斜不变,1.2.2.2 天平倾斜改变。
1.2.2.1 天平倾斜改变,说明问题出在(4,5)球。
第三步 (4)vs (?)
得到结果:如果平衡,5号是次球。
如果不平衡,4号是次球。
1.2.2.2天平倾斜不变,说明问题出在(1,2,3)球。且可知次球轻重。
第三步 (1) vs (2)
得到结果: 如果平衡,3号是次球。
如果不平衡,根据次球轻重可知2或1号是次球。
感谢以上提到的各位老师和科学网的众博主的支持和关注。
注:应行仁老师已给出该问题的通解,请见:http://blog.sciencenet.cn/blog-826653-658533.html
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-1 11:23
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社