称球问题及其推广.docx
- 文档编号:4045407
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:41
- 大小:33.38KB
称球问题及其推广.docx
《称球问题及其推广.docx》由会员分享,可在线阅读,更多相关《称球问题及其推广.docx(41页珍藏版)》请在冰点文库上搜索。
称球问题及其推广
称球问题及其推广
称球问题一
有十二个小球特征相同,其中只有一个质量异常,要求用一部没有砝码的天平称三次,将那个质量异常的球找出来。
从信息论来看,12个球一个重量异常,出现概率1/12;该球质量可能轻也可能重,那么出现概率为1/2。
那么要得到结果所需信息量为log2+log12。
称一次可能有轻、重、相等三种结果,信息量为log3。
log24/log3<3,三次应该能称出来。
异常球出现概率1/12;该球质量可能轻也可能重,那么出现概率为1/2,就是说异常球为轻时,概率为1/24,为重时也是1/24,最后你知道哪个球异常,必然也必须知道它是重于一般球还是轻于一般球,所以,你要在这24种可能中找到对的那一种可能,那么所需信息量为-log1/24=log(2*12),不知道这样解释对不对?
将球分为3组,每组4个,任取两组称一次,若两边等重,则异常球在其余一组中,通过8个正常球很容易找出异常球。
若两组不等重,假设A组重,B组轻。
取A组取两个,B组取一个为甲组;取A组一个、B组1个,正常球一个为乙组,进行称重。
若两者相等,没有进入甲乙两组的球中,可能是A组剩余那个超重或是B组剩余的两个轻,将乙组两个称重,若等重则A组剩余那个异常,否则两个中较轻的异常。
若甲组重,则甲组中的两个原A组的重或是乙组中原B组的轻,将A组那两个称重,若等重则乙组中原B组的球异常,否则A组中较重的为异常球。
若甲组轻,则甲组中原B组的异常或是乙组中原A组的异常,任取一个与正常球对比即可找出异常球。
称球问题二
原题为:
有十二个小球特征相同,其中只有一个质量异常,要求用一部没有砝码的天平称三次,将那个质量异常的球找出来。
解:
设标准小球质量为w,将12个小球依次编号为a1,a2,...,a12,分组为:
a1,a2,a3,a4为A1组
a5,a6,a7,a8为A2组
a9,a10,a11,a12为A3组
==(第一次)1选定任意2组--取A1,A2进行比较,如果
1A1=A2
则A1/A2组8个小球a1,a2,...,a8均为正常小球,质量均为w
则A3组为异常球组
重新分组为:
B1:
a9a10
B2:
a11a1
B3:
a12a2
====(第二次)取B2B3任意1组--B2与B1进行比较,如果
1.1B1=B2则B1B2为正常组,B3(a11,a2)为异常组,因为a2为正常球,所以异常球为a12
1.2B1 表达式EXP0: a9+a10 ========(第三次)取a9a10进行比较,如果 1.2.1a9=a10则a11为异常球 1.2.2a9! =a10则a11为正常球,根据EXP0,异常球质量小于正常球,即 a9与a10轻者为异常球 2 A1 得表达式1: EXP1: a1+a2+a3+a4 表达式2: EXP2: a9=a10=a11=a12=w 重新分组为: B1: a1,a2,a3 B2: a4,a5,a9 B3: a6,a7,a8 ====(第二次)取B1或B3与B2比较,以B1为例说明: 2.1B1 即: EXP4: a1+a2+a3 EXP5: a6=a7=a8=w 其中a9=w 关联EXP1: a1+a2+a3+a4 相减 a4<-a4+2w a4 则异常球为 a4 2.2B1>B2则B3为正常组 即: EXP6: a1+a2+a3>a4+a5+a9 EXP7: a6=a7=a8=w 其中a9=w 关联EXP1: a1+a2+a3+a4 转换EXP1: -a1-a2-a3-a4>-a5-a6-a7-a8 相加-a4>a4-2w a4>w 则异常球为 a4 2.3B1=B2则B3为异常组 得表达式3: EXP3: a1=a2=a3=a4=a5=w 关联 EXP1: a1+a2+a3+a4 得3w 即推出如下结论 1)异常球质量大于正常球 2)异常球在B3(a6,a7,a8)中 ========(第三次)比较任意的两个--a6,a7,如果 a6=a7,则异常球为a8 a6 a6>a7,则异常球为 a6 称球问题三 说明 这篇文章试图给出称球问题的一个一般的和严格的解答。 正因为需要做到一般和严格,就要考虑许多平时遇不到的特别情形,所以叙述比较繁琐。 如果对读者对严格的证明没有兴趣,可以只阅读介绍问题和约定记号的第一、第二节,以及第三节末尾27个球的例子,和第五节13个球和40个球的解法。 事实上所有的技巧都已经表现在这几个例子里了。 一、问题 称球问题的经典形式是这样的: “有十二个外表相同的球,其中有一个坏球,它的重量和其它十一个有轻微的(但是可以测量出来的)差别。 现在有一架没有砝码的很灵敏的天平,问如何称三次就保证找出那个坏球,并知道它比标准球重还是轻。 ” 这可能是网上被做过次数最多的一道智力题了。 它的一种解法如下: 将十二个球编号为1-12。 第一次,先将1-4号放在左边,5-8号放在右边。 1.如果右重则坏球在1-8号。 第二次将2-4号拿掉,将6-8号从右边移到左边,把9-11号放 在右边。 就是说,把1,6,7,8放在左边,5,9,10,11放在右边。 1.如果右重则坏球在没有被触动的1,5号。 如果是1号, 则它比标准球轻;如果是5号,则它比标准球重。 第三次将1号放在左边,2号放在右边。 1.如果右重则1号是坏球且比标准球轻; 2.如果平衡则5号是坏球且比标准球重; 3.这次不可能左重。 2.如果平衡则坏球在被拿掉的2-4号,且比标准球轻。 第三次将2号放在左边,3号放在右边。 1.如果右重则2号是坏球且比标准球轻; 2.如果平衡则4号是坏球且比标准球轻; 3.如果左重则3号是坏球且比标准球轻。 3.如果左重则坏球在拿到左边的6-8号,且比标准球重。 第三次将6号放在左边,7号放在右边。 1.如果右重则7号是坏球且比标准球重; 2.如果平衡则8号是坏球且比标准球重; 3.如果左重则6号是坏球且比标准球重。 2.如果天平平衡,则坏球在9-12号。 第二次将1-3号放在左边,9-11号放在右边。 1.如果右重则坏球在9-11号且坏球较重。 第三次将9号放在左边,10号放在右边。 1.如果右重则10号是坏球且比标准球重; 2.如果平衡则11号是坏球且比标准球重; 3.如果左重则9号是坏球且比标准球重。 2.如果平衡则坏球为12号。 第三次将1号放在左边,12号放在右边。 1.如果右重则12号是坏球且比标准球重; 2.这次不可能平衡; 3.如果左重则12号是坏球且比标准球轻。 3.如果左重则坏球在9-11号且坏球较轻。 第三次将9号放在左边,10号放在右边。 1.如果右重则9号是坏球且比标准球轻; 2.如果平衡则11号是坏球且比标准球轻; 3.如果左重则10号是坏球且比标准球轻。 3.如果左重则坏球在1-8号。 第二次将2-4号拿掉,将6-8号从右边移到左边,把9-11号放 在右边。 就是说,把1,6,7,8放在左边,5,9,10,11放在右边。 1.如果右重则坏球在拿到左边的6-8号,且比标准球轻。 第三次将6号放在左边,7号放在右边。 1.如果右重则6号是坏球且比标准球轻; 2.如果平衡则8号是坏球且比标准球轻; 3.如果左重则7号是坏球且比标准球轻。 2.如果平衡则坏球在被拿掉的2-4号,且比标准球重。 第三次将2号放在左边,3号放在右边。 1.如果右重则3号是坏球且比标准球重; 2.如果平衡则4号是坏球且比标准球重; 3.如果左重则2号是坏球且比标准球重。 3.如果左重则坏球在没有被触动的1,5号。 如果是1号, 则它比标准球重;如果是5号,则它比标准球轻。 第三次将1号放在左边,2号放在右边。 1.这次不可能右重。 2.如果平衡则5号是坏球且比标准球轻; 3.如果左重则1号是坏球且比标准球重; 够麻烦的吧。 其实里面有许多情况是对称的,比如第一次称时的右重和右轻,只需考虑一种就可以了,另一种完全可以比照执行。 我把整个过程写下来,只是想吓唬吓唬大家。 稍微试一下,就可以知道只称两次是不可能保证找到坏球的。 如果给的是十三个球,以上的解法也基本有效,只是要有个小小的改动,就是在这种情况下,在第一第二次都平衡的时候,第三次还是有可能平衡(就是上面的第2.2.2步),那么我们可以肯定坏球是13号球,可是我们没法知道它到底是比标准球轻,还是比标准球重。 如果给的是十四个球,我们会发现无论如何也不可能只称三次,就保证找出坏球。 一个自然而然的问题就是: 对于给定的自然数N,我们怎么来解有N个球的称球问题? 在下面的讨论中,给定任一自然数N,我们要解决以下问题: ⑴找出N球称球问题所需的最小次数,并证明以上所给的最小次数的确是最小的; ⑵给出最小次数称球的具体方法; ⑶如果只要求找出坏球而不要求知道坏球的轻重,对N球称球问题解决以上两个问题; 还有一个我们并不是那么感兴趣,但是作为副产品的问题是: ⑷如果除了所给的N个球外,另外还给一标准球,解决以上三个问题。 二、记号 我们先不忙着马上着手解决上述问题。 先得给出几个定义,尤其是,要给出比较简单的符号和记法。 大家看到上面给出的解法写起来实在麻烦——想象一下如果我们要用这种方法来描述称40个或1000个球的问题! 仍旧考虑十二个球的情况和上面举的解法。 在还没有开始称第一次时,我们对这十二个球所知的信息就是其中有一或较轻,或较重的坏球,所以以下24种情况都是可能的: 1.1号是坏球,且较重; 2.2号是坏球,且较重; …… 12.12号是坏球,且较重; 13.1号是坏球,且较轻; 14.2号是坏球,且较轻; …… 24.12号是坏球,且较轻。 没有其他的可能性,比如说“1、2号都是坏球,且都较重”之类。 当我们按上面解法“先将1-4号放在左边,5-8号放在右边”称过第一次以后,假设结果是右重,稍微分析一下,就会知道上面的24种情况中,现在只有8种是可能的,就是 1.1号是坏球,且较轻; 2.2号是坏球,且较轻; 3.3号是坏球,且较轻; 4.4号是坏球,且较轻; 5.5号是坏球,且较重; 6.6号是坏球,且较重; 7.7号是坏球,且较重; 8.8号是坏球,且较重。 我们把诸如“1号是坏球,且较重,其他球都正常”和“2号是坏球,且较轻,其他球都正常”这样的情况,称为一种“布局”,并记为: (1重) 和 (2轻) 我们把“先将1-4号放在左边,5-8号放在右边”这样的步骤,称为一次“称量”。 我们把上面这次称量记为 (1,2,3,4;5,6,7,8) 或 (1-4;5-8) 也就是在括号内写出参加称量的球的号码,并且以分号分开放在左边和放在右边的球号。 在最一开始,我们有24种可能的布局,而在经过一次称量(1-4;5-8)后,如果结果是右重,我们就剩下上述8种可能的布局。 我们的目的,就是要使用尽量少的称量,而获得唯一一种可能的布局——这样我们就知道哪个球是坏球,它是比较重还是比较轻。 这里我们注意到没有必要去考虑两边球数不相等的称量。 因为坏球和标准球重量之间的差别很小,小于标准球的重量,所以当天平两边球数不一样时,天平一定向球比较多的那边倾斜。 所以在进行这样一次称量之前,它的的结果就可以被预料到,它不能给我们带来任何 新的信息。 事实上在看完本文以后大家就很容易明白,即使坏球和标准球重量之间的差别很大,也不会影响本文的结论。 因为考虑这种情况会使问题变麻烦,而并不能带来有趣的结果,我们就省略对此的考虑。 现在我们看到,上面关于十二个球问题的解法,其实就是由一系列称量组成的——可不是随随便便的组合,而是以这样的形式构成的: 称量1 如果右重,则 称量3 …… 如果平衡,则 称量2 …… 如果左重,则 称量4 …… 省略号部分则又是差不多的“如果右重,则……”等等。 所以这就提示我们用树的形式来表示上面的解法: 树的根是第一次称量,它有三个分支(即三棵子树,于是根有三个子节点),分别对应着在这个称量下的右重、平衡、左重三种情况。 在根的三个子节点上,又分别有相应的称量,和它们的三个分支……如果具体地写出来,就是 |--右--(1轻) |--右--(1;2)|--平--(5重) ||--左--() | ||--右--(2轻) |--右--(1,6-8;|--平--(2;3)|--平--(4轻) |5,9-11)||--左--(3轻) || |||--右--(7重) ||--左--(6;7)|--平--(8重) ||--左--(6重) | ||--右--(10重) ||--右--(9;10)|--平--(11重) |||--左--(9重) || |||--右--(12重) (1-4;5-8)|--平--(1-3;|--平--(1;12)|--平--(13轻,13重)* |9-11)||--左--(12轻) || |||--右--(9轻) ||--左--(9;10)|--平--(11轻) ||--左--(10轻) | ||--右--(6轻) ||--右--(6;7)|--平--(8轻) |||--左--(7轻) || |||--右--(3重) |--左--(1,6-8;|--平--(2;3)|--平--(4重) 5,9-11)||--左--(2重) | ||--右--() |--左--(1;2)|--平--(5轻) |--左--(1重) (*: 对应十三个球的情形。 ) 这里“右”、“平”和“左”分别表示称量的结果为“右重”、“平衡”和“左重”所对应的分支。 在树的叶子(就是最右边没有子节点的那些节点)部分,我们标出了“能够到达”这些节点的布局,也就是说在进行每一节点上的称量时,这个布局所给的结果和通往相对应的叶子的道路上所标出的“右”、“平”和“左”相符合。 从这个图我们也可以清楚地看到,根下的左分支和右分支是对称的: 只需要把所有的“右”改成“左”,“左”改成“右”,“轻”改成“重”,“重”改成“轻”;节点(1-3;9-11)下的左分支和右分支也有这个特点。 (如果有朋友对树理论感兴趣,可以参考随便哪一本图论或者离散数学的书。 在这里我们只用到树理论里最基本的知识,所用的名词和结论都是相当直观的。 所以如果你不知道树理论,用不着特别去学也可以看懂这里的论证。 ) 所以给定一棵三分树(就是说除了叶子以外其他的节点都有三个子节点的树),在每个不是叶子的节点上给定一个称量,并且规定这个节点下的三个分支(子树)分别对应右重、平衡、左重的情况,我们就得到了一种称球的方法。 我们把这样一棵三分树称为一个“策略”或一棵“策略树”。 你可以给出一个平凡的策略,比如说无论发生了什么事总是把1号和2号球放在左右两侧来称(在叶子上我们没有写出相应的布局,用@来代替): |--右--@A |--右--(1;2)|--平--@ ||--左--@ | ||--右--@ (1;2)|--平--(1;2)|--平--@ ||--左--@ | ||--右--@B ||--右--(1;2)|--平--@ |||--左--@ || |||--右--@ |--左--(1;2)|--平--(1;2)|--平--@ ||--左--@ | ||--右--@ |--左--(1;2)|--平--@ |--左--@ 当然这么个策略没什么用场,只能让我们知道1号球和2号球之间的轻重关系。 另外我们看到,每个分支不一定一样长,上面这棵策略树根下面左分支就比较长。 一棵树的高度是叶子到根之间的结点数的最大值加一。 比如说上面这个图中,叶子A和根间有1个节点,而叶子B和根间有2个节点,没有和根之间的节点数超过2的叶子。 所以它的高度是2+1=3。 前面十二球解法策略树的高度也是3。 一棵没有任何分支,只有根节点的树,我们定义它的高度是0。 显然,策略树的高度就是实行这个策略所需要的称量的次数。 我们的目的,就是找到一棵“好”的策略树,使得它的高度最小。 什么是“好”策略? 我们回过头来再看十二球解法策略树。 我们说过,叶子上的那些布局都是从根开始通向叶子的。 比如说布局(7重),它之所以在那片叶子上是因为按照这个策略,三次称量的结果是“右左右”;又比如说布局(11重),它之所以在那片叶子上是因为按照这个策略,三次称量的结果是“平右平”。 如果两个布局通向同一片叶子,那么就是说按照这个策略,三次称量的结果是完全一样的,于是我们就不能通过这个策略来把这两种布局区分开来。 比如说在十三个球的情况下,(13轻)和(13重)都通向和“平平平”相对应的叶子,这两个布局中13号球或者轻或者重,于是我们知道13号球一定是坏球,但是通过这个策略我们不可能知道它到底是轻还是重。 所以对于标准的称球问题(找出坏球并知其比标准球重或轻)的“好”策略,就是那些能使不同的布局通向不同的叶子的策略。 三、每个球都已知可能为轻或可能为重的情况 先引入一个记号: 对于任意实数a,我们用{a}表示大于等于a的最小整数,比如说{2.5}=3,{4}=4;我们用[a]表示小于等于a的最大整数,比如说[2.5]=2,[4]=4。 我们首先考虑这样一种布局的集合。 假设m,n为两个非负实数,不同时为0。 在编号从1到m+n的m+n个球中,我们知道1到m号球要么是标准球,要么比标准球重,而m+1到m+n号球要么是标准球,要么比标准球轻;我们还知道其中有一个是坏球(但不知轻重)。 换句话说,我们知道真实的情况是以下m+n种布局之一: 1.1号是坏球,且较重; 2.2号是坏球,且较重; …… m.m号是坏球,且较重; m+1.m+1号是坏球,且较轻; m+2.m+2号是坏球,且较轻; …… m+n.m+n号是坏球,且较轻。 有一种特殊的情况是m=0或n=0,也就是说坏球的是轻还是重已经知,常常被用来单独作为智力题。 结论1: 1)在以上条件成立的情况下,要保证在m+n个球中找出坏球并知道 其轻重,至少需要称{log3(m+n)}次。 2)如果m和n不同时为1,那么称{log3(m+n)}次就足够了。 如果 m=n=1,并且另有一标准球,那么称{log3(m+n)}={log3(1+1)}=1 次也足够了。 这里log3表示以3为底的对数。 需要对2)作点说明。 如果m=n=1而没有标准球的话,那么是永远也称不出坏球来的。 把两个球一边一个放在天平上,必然是1号重2号轻。 但是由于没有标准球,我们无法知道是坏球比较重所以1号是坏的,还是坏球比较轻所以2号是坏的。 如果有标准球,只要把1号球和标准球比较一下。 如果天平不平衡,那么1号球是坏球,且比较重;如果天平平衡,那么2号球是坏球,且比较轻。 策略树如下: (用s表示标准球) |--右--() | | (1;s)|--平--(2轻) | | |--左--(1重) 现在来证明1)。 在上面我们看到,可能的布局是m+n种(1重,2重,……,m重,m+1轻,m+2轻,……,m+n轻)。 假设我们已经有一个策略能保证在这m+n个球中找出坏球并知道其轻重,那么每一个布局都要通向策略树上的不同叶子,这棵策略树至少需要有m+n片叶子。 但是一棵高度为H的三分树最多只能有3H片叶子。 于是这棵策略树必须满足条件 3H≥m+n 也就是 H≥log3(m+n) 考虑到H是整数,我们就证明了 H≥{log3(m+n)} 现在我们要具体找到一棵高度为{log3(m+n)}的策略树,使得m+n种布局通向它的不同叶子。 我们对k=m+n使用数学归纳法。 首先k=1。 那么称都不要称,因为必有一坏球,那么坏球就是唯一的1号球。 如果是m=1,n=0,那么1号球比较重;如果是m=0,n=1,那么1号球比较轻。 需要的称量次数为{log3 (1)}=0。 对于k=2。 m=1,n=1的情况已经讨论过了。 考虑m=2,n=0。 这时我们知道坏球比较重。 只要把1号球和2号球放在天平两边一称,哪个比较重哪个就是坏球。 策略树如下: |--右--(2重) | | (1;2)|--平--() | | |--左--(1重) m=0,n=2的情况完全类似。 假设对于m+n<k的情况我们都可以用{log3(k)}次称出坏球。 考虑m+n=k的情况。 我们把1到m号球称为第一组球,m+1到n号球称为第二组球。 设H={log3(m+n)}={log3(k)}。 那么我们有 3H-1<k≤3H 3H-2<k/3≤3H-1 3H-2<{k/3}≤3H-1 于是 {log3{k/3}}=H-1。 现在我们把这k个球分为三堆,第一堆和第二堆分别有{k/3}个球,并且这两堆中属于第一组的球的数目一样(于是属于第二组的球的数目也一样),第三堆中有k-2{k/3}个球(也就是其余的球)。 举一个例子,如果m=7,n=3,那么这三堆可以分成这样: (当然不是唯一的分法) 第一堆: 1,2,3,7 (属于第一组的3个,第二组的1个) 第二堆: 4,5,6,8 (属于第一组的3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 问题 及其 推广