奥赛专题 -- 称球问题

称球问题——经典智力题推而广之三（五）五、四十个球的例子最后我们来解决一下40个球，没有标准球的问题。

我们知道40 = (34-1)/2所以我们可以称4次找出坏球，但是因为没有标准球，就不一定能知道坏球的轻重。

顺便先考虑13个球，另有一标准球的问题。

13 = (33-1)/2所以称3次可以找出坏球，因为有标准球，我们还可以同时知道坏球的轻重。

根据上一节的证明过程，这时我们要把这13个球分为3堆：第一堆：1-5第二堆：6-9，再加上标准球s第三堆：10-13我们把第一和第二堆小球放在天平左右端进行第一次称量。

如果是左边重，那么要么是第一堆1-5号球中有一个是坏球，而且它比标准球重，要么是第二堆6-9号球中有一个是坏球，那么它比标准球轻。

用结论1来解决的问题，第三节末尾我们处理过27个球的问题，9个球的问题就是小菜了：|--右--( 4重)|--右--(3 ; 4)|--平--( 6轻) | |--左--( 3重)|| |--右--( 8轻)(1-2,6;3-4,7)|--平--(8 ; 9)|--平--( 5重)| |--左--( 9轻)|| |--右--( 2重)|--左--(1 ; 2)|--平--( 7轻)|--左--( 1重)如果是右边重，那么和上面的情况对称，只要把策略树中的“左”和“右”互换，“轻”和“重”互换即可。

如果平衡，那么就化为4个球有一个标准球2次称出的问题。

虽然还可以往下照葫芦画瓢地递归一次，不过4个球的情况就太简单了，所以直接写出策略树：|--右--(10轻)|--右--(10;11)|--平--(12重)| |--左--(11轻)|| |--右--(13轻)(10,11;12,s)|--平--(13; s)|--平--( )| |--左--(13重)|| |--右--(11重)|--左--(10;11)|--平--(12轻)|--左--(10重)把左中右三个分支拼起来我们就得到13个球有一标准球称3次的策略树：|--右--( 1轻) |--右--(1 ; 2)|--平--( 7重)| |--左--( 2轻)|| |--右--( 9重)|--右--(1-2,6;|--平--(8 ; 9)|--平--( 5轻)| 3-4,7)| |--左--( 8重)| || | |--右--( 3轻)| |--左--(3 ; 4)|--平--( 6重)| |--左--( 4轻)|| |--右--(10轻)| |--右--(10;11)|--平--(12重)| | |--左--(11轻)| || | |--右--(13轻)(1-5; |--平--(10,11;|--平--(13; s)|--平--( )6-9,s)| 12,s)| |--左--(13重)| || | |--右--(11重)| |--左--(10;11)|--平--(12轻)| |--左--(10重)|| |--右--( 4重)| |--右--(3 ; 4)|--平--( 6轻)| | |--左--( 3重)| || | |--右--( 8轻)|--左--(1-2,6;|--平--(8 ; 9)|--平--( 5重)3-4,7)| |--左--( 9轻)|| |--右--( 2重)|--左--(1 ; 2)|--平--( 7轻)|--左--( 1重)现在可以考虑40个球，无标准球的问题了。

1、海盗分金问题传说，从前有五个海盗抢得了100枚金币.他们通过了一个如何确定选用谁的分配方案的安排.即：1.抽签决定各人的号码（1，2，3，4，5）；2.先由1号提出分配方案，然后5个人表决.当且仅当超过半数人同意时，方案才算被通过，否则他将被扔入大海喂鲨鱼；3.当1号死后，再由2号提方案，4个人表决，当且仅当超过半数同意时，方案才算通过，否则2号同样将被扔入大海喂鲨鱼；4.往下依次类推……根据上面的这个故事，现在提出如下的一个问题.即：我们假定每个海盗都是很聪明的人，并且都能够很理智地判断自己的得失，从而做出最佳的选择，那么第一个海盗应当提出怎样的分配方案才能够使自己不被扔入大海喂鲨鱼，而且收益还能达到最大化呢？2、帽子问题（疯狗问题与此同理）一群人开舞会，每人头上都戴着一顶帽子。

帽子只有黑白两种，黑的至少有一顶。

每个人都能看到其他人帽子的颜色，却不知自己的。

主持人先让大家看看别人头上戴的什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。

第一次关灯，没有声音。

于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。

一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。

问有多少人戴着黑帽子？参考：3、称球问题一共12个一样的小球，其中只有一个重量与其它不一样(未知轻重)，给你一个天平，只称三次，找出那个不同重量的球？如果一共13个一样的小球，其中只有一个重量与其它不一样(未知轻重)，给你一个天平，只称三次，找出那个不同重量的球？参考：4、分金条问题你让某些人为你工作了七天，你要用一根金条作为报酬。

这根金条要被分成七块。

你必须在每天的活干完后交给他们一块。

如果你只能将这根金条切割两次，你怎样给这些工人分？5、猴子搬香蕉问题一个小猴子边上有100根香蕉，它要走过50米才能到家，每次它最多搬50根香蕉，每走1米就要吃掉一根，请问它最多能把多少根香蕉搬到家里参考：6、飞机加油问题每个飞机只有一个油箱，飞机之间可以相互加油（注意是相互，没有加油机）一箱油可供一架飞机绕地球飞半圈。

市秤的称球问题【提问】有十二个大小相等的球,除开一个之外,其余各个质量相等.现在要用天平把那个质量不同的球称出来,只许称三次,并且要确定它是轻些或者重些,问应怎样称?这个问题用天平已经解决,不过通常不容易找到天平,手边常有的只是买菜的市秤（目前广泛采用的是电子秤）,它的效用与弹簧秤一样,现在问,如果不用天平只许用市秤,上述问题的解法如何?听说十二个球保证找出一个差异球要称四次,怎么称？进一步，十五个球保证选出一个差异球怎么称呢？【解答】以下为了方便起见,那个质量不同的球叫做坏球,其余质量相同的球叫做好球,再假定球的总数是N,要称的次数是n。

先从简单的情形开始。

【定理1】如果好球与坏球的质量都是已知的,n次就可以称2∧n个球。

证明分两个步骤：(1)当N=1的时候,因为坏球的个数是1,所以不必称。

这就是说n=0的时候，定理是正确的。

(2)应用数学归纳法,假定n次可称2∧n个球,试证n+1次可称2∧（n+1）个球。

这是因为在2∧（n+1）个球中任意取出2∧n个球放在秤盘中,如果恰是好球质量的2∧n倍,坏球在盘外2∧n个球中,如果不是好球质量的2∧n倍,坏球在盘上2∧n个球中。

两种情形,根据归纳假设,都只要再称次就可以找出坏球。

【定理2】当好球质量是已知的,n次就可以称2∧（n+1）个球,并且可以找出坏球质量。

证明分两个步骤：(1)当N=1的时候,因为坏球的个数是1,所以没有好球。

这时只称一次就可以知道它的质量,也就是说当n=1的时候,定理是正确的。

(2)应用数学归纳法,假定n次可称2∧（n+1）个球,试证n+1次可称2∧（n+1）-1个球。

这是因为在2∧（n+1）-1个球中任意取出2∧n个球放在秤盘中,如果恰是好球质量的2∧n 倍,坏球在盘外2∧（n+1）-1球中,根据归纳假设再称,次就可以找出坏球。

如果不是好球质量的2∧n倍,坏球在盘上2∧n个球中,根据定理1,再称n次也可以找出坏球,因此定理得证。

我将首先致力于解决下面的问题：问题：已知 N 个球中有1个是坏的，但不知轻重，问用天平至少称多少次可以把它找出来，并判断轻重？在解决这个问题之后，将是此问题的一些推广，关于非随机应变策略，关于多臂天平，以及关于多个坏球等等。

从一个最简单的问题开始问题：假设三个球中有一个不标准,且已知是重的,则可以称几次将非标准球找出来？假设三个球中有一个不标准,且已知是重的,则可以称一次将非标准球找出来。

方法是随便取两个来称，如果天平平衡，则第三个球是坏的，如果天平不平衡，则较重的那个球是坏的。

那么，如果是9个球的话，又如何呢？假设9个球中有一个不标准,且已知是重的,则可以称2次将非标准球找出来。

方法是把9个球分成3组A,B,C，第一次称其中两组(A vs B)，如果天平平衡，说明坏球在C组，如果天平不平衡，则坏球在较重的那一组中，然后问题归结为3个球的情况假设3^k个球中有一个不标准,且已知是重的,则可以称k次将非标准球找出来。

或者说：【定理】假设 N 个球中有一个不标准,且已知是重的,则可以称{log3(N)}次将非标准球找出来。

======找不到上取整符号，我用{}表示上取整，=====好了，这是我们得到的第一个一般性的结论。

为了严密起见，我将严格的证明它。

我需要证明的是下面两条：1.N<=3^k时，可以称k次把坏球找出来。

2.N>=3^k+1时，称k次不能必然把坏球找出来。

1.N<=3^k时，可以称k次把坏球找出来。

首先说明一个平凡的情况：N=1此时，既然已经知道有一个坏球，而又只有一个球，则它自然就是坏球也就是说称0次可以把它找出来，因而命题成立。

下面用归纳法证明，对k归纳(1)k=1时此时N=1，2或3N=1时不用说了N=2时，有两个球A,B，则称A vs B，较重的那个是坏的，一次就可以把坏球找出来N=3时, 见3L。

也是一次就可以把坏球找出来。

(2)假设对k-1命题成立，即N<=3^(k-1)时，可以称k-1次把坏球找出来。

开放经济名词解释
嘿，朋友！你知道啥是开放经济不？开放经济啊，就好比是一个超
级大的舞台！（就像世界是个大舞台，各国都在上面尽情展示自己。

）在这个舞台上，各个国家不再是自己玩自己的，而是相互交流、合作、竞争。

想象一下，每个国家都像是一个独特的演员，有着自己的
特色和本领。

（比如说有的国家擅长制造高科技产品，有的国家资源
丰富。

）
贸易就是这个舞台上很重要的一部分呀！各国把自己的好东西拿出
来卖，同时也能买到别人的好东西。

这多棒啊！（这不就像你去市场，用自己的苹果换别人的香蕉嘛。

）而且呀，开放经济下，资金也能自
由流动呢！钱就像一群小精灵，在各个国家之间欢快地跑来跑去。

（资金从一个国家跑到另一个国家去投资，寻求更好的回报。

）人才也能在开放经济中自由流动哦！那些有才华的人可以去自己想
去的地方，发挥自己的才能。

（就像一个优秀的音乐家，可以去世界
各地演出，展示自己的技艺。

）
开放经济可不是随随便便就能玩得转的哟！它需要一系列的规则和
制度来保障。

（就像一场比赛，得有裁判和规则，不然不就乱套啦。

）各个国家要相互尊重、遵守规则，这样才能让这个舞台更加精彩。

你说，要是没有开放经济，我们的生活得少多少乐趣和便利呀？我
们能用到世界各地的好东西，不就是因为开放经济嘛！所以呀，开放
经济真的超级重要的！它让我们的世界变得更加丰富多彩，让我们能享受到更多的好东西！总之，开放经济就是让世界紧密联系在一起的神奇力量！。

称球问题——经典智力题推而广之三（三）三、每个球都已知可能为轻或可能为重的情况先引入一个记号：对于任意实数a，我们用{a}表示大于等于a的最小整数，比如说{}=3，{4}=4；我们用[a]表示小于等于a的最大整数，比如说[]=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号球是坏球，且比较轻。

策略树如下：|--右--( )||(1; s)|--平--(2轻)|||--左--(1重)现在来证明1)。

在上面我们看到，可能的布局是m+n 种。

假设我们已经有一个策略能保证在这m+n个球中找出坏球并知道其轻重，那么每一个布局都要通向策略树上的不同叶子，这棵策略树至少需要有m+n片叶子。

序古老的智力题详述:有12个球特征相同,其中只有一个重量异常,要求用一部没有砝码的天平称三次,将那个重量异常的球找出来。

以下会给4个解答，一个比一个牛，一个比一个震撼！第一篇先给个被号称网上最牛的解答，一种新的完全的数学解法（线代+信息论），该文解法创于2005年，一次与友人聊天建议发表到QQ346546618的个人空间（2006年7月），后被网友转载到各大网站并被收入到百度文库。

第二篇会给个EXCEL进阶解法，网友们可以用此法加上分块矩阵的方法继续找出9球称4次找2异常球的具体解法或更复杂的称球问题。

第三篇会给出2个很漂亮完美的非常特别的解，其称量结果的三进制和异常球序号及和轻重状态具有简洁的一一对应关系。

第一篇（学好数理化走遍天下都不怕）原文：网上的最多的方法是逻辑法,还有少数画成图的所谓策略树和基于此的程序算法.这里我提出一种新的完全的数学解法:一·首先提出称量的数学模型:把一次称量看成一个一次代数式,同样问题就可以描述成简单的矩阵方程求解问题.怎么把一次称量表示成一个代数式呢?1),简化描述小球的重量(状态)----正常球重量设为0,设异常球比正常球重为1或轻为-1,异常球未知轻重时用x代表(只取1或-1).用列向量j表示所有球的重量状态.2),简化描述称量的左右(放法)-----把某号球放左边设为1,右边设为-1,不放上去设为0.用行向量i表示某次称量所有球的左右状态.3),描述称量结果:由1),2)已经可以确定一个称量式∑各球的重量*放法=天平称量结果.--------(1)式如果我们用向量j,i分别表示球的重量状态和球的左右放法情况(j为行向量,i为列向量),对于(1)式,可以改写为j*i=a(常数a为单次称量结果) -------------(2)式例如有1-6号共6个小球,其中4号为较重球,拿3号5号放左边,1号4号放右边进行称量,式子为:(-1)*0+0*0+1*0+(-1)*1+1*0+0*0=-1,从-1的意义可以知道它表示结果的左边较轻;同样可以得到0表示平衡,1表示左边较重.4),方程用来描述称量过程,还需附加一个重要的条件:代表放左边的1和右边的-1个数相等,也就是∑各球的放法=0-------------------------(3)式这样就解决了称量的数学表达问题.对于12个小球的3次称量,分别用12维行向量j1,j2,j3表示,由j1j2j3便构成了3×12的称量矩阵J；对于某一可能情况i,对应的3次称量结果组成的3维列向量b,得J*i=b二·称球问题的数学建模问题的等价：设J为3×12的矩阵，满足每行各项之和为0。

称球问题——经典智力题推而广之三（二）二、记号我们先不忙着马上着手解决上述问题。

先得给出几个定义，尤其是，要给出比较简单的符号和记法。

大家看到上面给出的解法写起来实在麻烦——想象一下如果我们要用这种方法来描述称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种可能的布局。

我们的目的，就是要使用尽量少的称量，而获得唯一一种可能的布局——这样我们就知道哪个球是坏球，它是比较重还是比较轻。

这里我们注意到没有必要去考虑两边球数不相等的称量。