经典称球问题.doc

我将首先致力于解决下面的问题：问题：已知 N 个球中有1个是坏的，但不知轻重，问用天平至少称多少次可以把它找出来，并判断轻重？在解决这个问题之后，将是此问题的一些推广，关于非随机应变策略，关于多臂天平，以及关于多个坏球等等。 我也说一句从一个最简单的问题开始问题：假设三个球中有一个不标准,且已知是重的,则可以称几次将非标准球找出来？个人企业举报垃圾信息举报我也说一句假设三个球中有一个不标准,且已知是重的,则可以称一次将非标准球找出来。方法是随便取两个来称，如果天平平衡，则第三个球是坏的，如果天平不平衡，则较重的那个球是坏的。那么，如果是9个球的话，又如何呢？假设9个球中有一个不标准,且已知是重的,则可以称2次将非标准球找出来。方法是把9个球分成3组A,B,C，第一次称其中两组(A vs B)，如果天平平衡，说明坏球在C组，如果天平不平衡，则坏球在较重的那一组中，然后问题归结为3个球的情况 我也说一句假设3k个球中有一个不标准,且已知是重的,则可以称k次将非标准球找出来。或者说：【定理】假设 N 个球中有一个不标准,且已知是重的,则可以称log3(N)次将非标准球找出来。=找不到上取整符号，我用表示上取整，=好了，这是我们得到的第一个一般性的结论。为了严密起见，我将严格的证明它。我需要证明的是下面两条：1.N=3k+1时，称k次不能必然把坏球找出来。我也说一句 我也说一句 我也说一句 我也说一句1.N=3k时，可以称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次把坏球找出来。当N=3k时，首先将N个球平均分成A,B,C 3份(此处“平均”是指每两份之间相差不超过1个)容易知道，|A|,|B|,|C|都=3(k-1)，并且其中有两组球个数相等（有可能三组球个数都相等）我们取出两组个数相等的球，不妨设为A,B第一次 称 A vs B如果天平平衡，说明坏球在C组中，如果天平不平衡，说明坏球在A,B中较重的那一组中总之，我们把坏球限制在A,B,C中的一组当中由于每一组球的个数都=3(k-1),由归纳假设，我们可以用k-1次从A(或BC)中将坏球找出来因此我们可以用k次从N=3k+1时，称k次不能必然把坏球找出来。这个涉及到信息论，简单来说就是一共有3k+1种可能的结果，每一次称量可以从3组（互不相容的）信息中选出一种因此k次称量最多可以从3k种不同的结果中选出一种所以 N=3k+1时，称k次不能必然把坏球找出来。=或者说我们有这样一个原理：如果要从M种可能的情况中确定一种情况，又每次测量有a个结果，则最少需要测量loga(M) 次。当然实际需要的次数可能更多，因为你不能保证每次都得到“有用”的信息。但是 loga(M) 是所需次数的一个下界，我们把这个值称为【信息论下界】=回到4L的定理，我们有相对应的一个结论【定理】假设 N 个球中有一个不标准,且已知是轻的,则可以称log3(N)次将非标准球找出来。现在，在已知坏球轻重的情况下，我们得到了把坏球找出来的最少次数 我也说一句假设3k个球中有一个不标准,其中一部分已知不重,另一部分已知不轻,则可以称k次将非标准球找出来,并判定其轻重.假设3k个球中有一个不标准,且这3k个球一部分已知不重,另一部分已知不轻,则可以称几次将非标准球找出来？=所谓某个球不重是指这个球或者是标准的，或者是坏的但比标准球轻=首先这个问题的信息论下界是 k 次，那么k次能把坏球找出来吗？ 我也说一句首先解决LS提出的问题：假设N=3k个球中有一个不标准,其中一部分已知不重,另一部分已知不轻,则可以称k次将非标准球找出来,并判定其轻重.（注意此处我没说N(3k-1)/2的话N=(3k+1)/2由信息论下界知称k次是不能将非标准球找出来,并判定其轻重的。） 我也说一句在归纳假设中，我假设命题对k-1成立，意思是对N=3(k-1)个球，只要满足命题条件，都可以用k次将坏球找出来。或者说，3(k-1)分成两组，一组已知不重，一组已知不轻，（不论满不满足情形1）都可以用k次将坏球找出来。收起回复收起回复 我也说一句吧友58.61.56.*我看到13L的时候发现自己对不重不轻这两个概念理解不能k=1，N=3个球,共有四种情况(1) 全部不重 (2)全部不轻 (3) 两个球不重，一个球不轻 (4) 两个球不轻，一个球不重什么叫全部不重？什么叫全部不轻？ 我也说一句吧友58.61.56.*全部不重是指三个球全部不重于标准球？那就是坏球是轻球？那么两个不重，一个不轻又是指什么呢？有两个球不重于标准球，如果它们中有一个是坏球，那么坏球是轻球；如果不是，则坏球是不轻的那个球，也就是重球。同样的，两个不轻，一个不重，则坏球分别是重球和轻球。是不是这样？ 我也说一句吧友58.61.56.*不知道为什么LZ要造出这两个概念来三个球，有一个是坏的，不是轻就是重。什么叫不轻？什么叫不重？这种题目总是用三分法来做的吧？分成三部分，两个一称，平的话在第三堆，不平的话则在这两堆中。然后继续判断。 我也说一句 我也说一句吧友58.61.56.*假设一次能一堆一堆的称，则球的总数目为3K情形的：均分三堆，称两次知道坏球在哪一堆，不可能更省（要包括最坏情形）令SI表示第I次得到的坏球那一堆的数目以及HI为此时已用的称量次数则HI=2I，SI=3(K-I)I=K时，HI=2K,SI=1。称量完毕。至于轻重，在上述的称法中每得到下一个SI时即已得出。无需再称。然后不明白LZ为什么写那么多来说明这种能够一堆一堆的称，并且球总数还为3K的情况回复 收起回复 我也说一句吧友58.61.56.*证明：A,B,C三堆。第一次：AB。若平，说明是C。若不平，C是好的。然后称第二次：第二次：AC。若平，说明是B；若不平，说明是A。由于ABC只是任意相同数目的堆，所以对于此类三等均分情形均得证另外：第一次中知道是C，但不知轻重。第二次就一定知道。不会运气好的这么离谱，每次都一次直接找出吧？ 我也说一句吧友61.150.43.*在14L的结论中，我们说过，对N=2是不成立的，实际上这是唯一的一个特例，我们有：假设3=N=3k个球中有一个不标准,其中一部分已知不重,另一部分已知不轻,称k次将非标准球找出来,并判定其轻重.另外，对于N=2的情况，借助一个标准球也可以一次将非标准球找出来。这个证明略。 现在证明这个：假设N(3k-1)/2个球中有一个不标准,且不知其轻重,则可以借助一个标准球称k次将非标准球找出来,并判定其轻重.对k归纳。k=1时，N=1.用标准球与这一个球称一次就可以了。假设命题对=k-1,成立，则对N(3k-1)/2个球将球平均分成3组A,B,C,（平均指每两组个数相差不超过1），则每组个数=(3k+1)/2 ）或者说，至多有一组个数=(3(k-1)+1)/2。不妨设A组个数最多。（|B|,|C|=(3(k-1)-1)/2 ）第一次，称A vs B （如果|B|A|的话，在B中加上那个标准球）如果天平平衡，则说明坏球在C组中，由归纳假设，可以用k-1次将非标准球找出来并判断其轻重（借助标准球）如果天平不平衡，不妨设A重B轻。则(1)非标准球在A和B中，C中的都是标准球。 (2)2=|A|+|B|=3(k-1).我们取A,B两组的所有球则坏球在这N（3=N=3个球中有一个不标准,且不知其轻重,则可以称log3(2N+3)次将非标准球找出来,并判定其轻重.或者说k次可以从至多 (3k-3)/2 个球中将坏球找出来，并判断其轻重。（这个数列的前几项是 a2=3, a3=12, a4=39, a5=120 .）下面我证明两条：1.或者说k次可以从 N=3)。2.N=(3k-1)/2个球，用k次是不能将坏球找出来，并判断其轻重的。证明1. k=1是没有意义的，k=2.将 N=(3k-3)/2 个球平均分成3份，则每份最多有 (3(k-1)-1)/2 个球，并且有两份数目相等。设A,B,C三组，A,B相等。（另外，每组至少有一个球）第一次 A vs B如果平衡，说明坏球在C组，而且我有了一个标准球。又 |C|=(3(k-1)-1)/2,根据29L的结论，我可以用k-1次将坏球找出来并判断其轻重。如果不平衡，则坏球在A,B中，并且我已知了一部分不重，另一部分不轻，而且我有了一个标准球。又 |A|+|B|=(3k+1)/2，则所需次数的信息论下界log3(2N)=k+1，因此k次显然不够。 下面假设 N=(3k-1)/2由于每次称量天平的两边必须放相同数目的球（否则得不到确定的信息），假设第一次 A vs B，对第一次称球的数目分两种情况讨论，情形1：|A|=|B|=(3(k-1)+1)/2，如果A,B平衡的话，我需要在C组中找出坏球并判断其轻重。 而这时的信息论下界至少为log3(3(k-1)+1)=k。 所以至少需要k次。这种情况下共需k+1次。情形2：|A|=|B|=(3(k-1)+1)/2,在这种情形下，如果A,B不平衡的话，则坏球在A,B中，（当然我可以知道一部分不重，另一部分不轻），但A,B球总数=3(k-1)+1，因此这时的信息论下界至少为log3(3(k-1)+1)=k。 所以至少需要k次。这种情况下共需k+1次。总之，我不能只用k次将坏球找出来并判断其轻重。 我也说一句吧友61.150.43.*现在，我完全回答了这个问题假设N个球中有一个不标准,且不知其轻重,则可以称多少次将非标准球找出来,并判定其轻重呢，是 log3(2N+3) 次。实际上，当N=3k（k较大时），log3(2N+3)=k+1（即不知球轻重的情形下，需要比已知球轻重的情形多称一次）以9个球，其中一个坏球，不知轻重为例：分成三组，A、B、C，先称A和B，1. A和B平衡，则坏球在C中，再多称一次A和C,即可判断出坏球是轻还是重，归结为已知球轻重的情形。2. A和B不平衡，不妨假设AB,再称B和C：3.4.5.6. 若B和C平衡，则说明坏球在A中，且是重球，7. 若CB，说明坏球在B中，且是轻球，若BC，此种情形不可能出现。8.9.10.11.12. 亦归结为已知球轻重的情形。证毕。 13.14.15.16.17.18.19.20.21.22. 当我们不要求判断轻重的情况下，又需要多少次呢？或者说，k次最多可以从多少个球里找出坏球呢？(首先说这个的信息论下界是log3(N),而并非log3(2N),因为只有N种可能的结果）答案是 k次最多可以从 (3k-1)/2 个球里找出坏球.（与需要判断轻重的情况比较，仅仅多1个球）我也说一句我来试着根据楼主的思路接着证明最这个问题吧，但得事先加一个独立在试验球数之外的标准球。构造方式如下：k=0和k=1时是个平凡解。k=2时，(3k-1)/2=4。从4个球中任取2个球a,b放在天平上，若a,b平衡则坏球在剩下的2个球c,d里，此时标准球是a,b，用标准球能轻易比较出c,d谁是坏球。（因为不需要知道轻重）；若a,b不平衡则坏球在a,b里，此时标准球是c,d，同理用标准球能轻易比较出c,d谁是坏球。不妨设k=n-1时命题成立，其中n可取大于3的任意自然数，即(3(n-1)-1)/2个球能用n-1次称出坏球来，现在构造k=n的情况：将(3n-1)/2个球均分为每份差小于等于1的3份，显然最大的1份(不妨设为集合A)为(3(n-1)+1)/2 ,同时较小的2份（设为集合B,C）一定相等且为(3(n-1)-1)/2。首先任取一份较小的，不妨取B,并加上一个标准球,和A称重(注意|B|=|C|=|A-1|=(3(n-1)-1)/2)，若天平平衡，则坏球在余下较小的那份，即C里，由归纳归纳可得结论成立。若天平不平衡，不妨设倾向A（倾向B结论一样），此时可知所有A里的小球非轻，并且所有B里的小球非重，并且|A|+|B|=(3(n-1)-1)/2 +(3(n-1)+1)/2 =3(n-1)。此时由29L的结论可得结论成立。显然以上归纳了每一种原命题的情况。我来试着根据楼主的思路接着证明最后这个问题吧:k次最多可以从多少个球里找出坏球.事先加一个独立在试验球数之外的标准球。构造方式如下：k=0和k=1时是个平凡解。k=2时，(3k-1)/2=4。从4个球中任取2个球a,b放在天平上，若a,b平衡则坏球在剩下的2个球c,d里，此时标准球是a,b，用标准球能轻易比较出c,d谁是坏球。（因为不需要知道轻重）；若a,b不平衡则坏球在a,b里，此时标准球是c,d，同理用标准球能轻易比较出c,d谁是坏球。不妨设k=n-1时命题成立，其中n可取大于3的任意自然数，即(3(n-1)-1)/2个球能用n-1次称出坏球来，现在构造k=n的情况：将(3n-1)/2个球均分为每份差小于等于1的3份，显然最大的1份(不妨设为集合A)为(3(n-1)+1)/2 ,同时较小的2份（设为集合B,C）一定相等且为(3(n-1)-1)/2。首先任取一份较小的，不妨取B,并加上一个标准球,和A称重(注意|B|=|C|=|A-1|=(3(n-1)-1)/2)，若天平平衡，则坏球在余下较小的那份，即C里，由归纳归纳可得结论成立。若天平不平衡，不妨设倾向A（倾向B结论一样），此时可知所有A里的小球非轻，并且所有B里的小球非重，并且|A|+|B|=(3(n-1)-1)/2 +(3(n-1)+1)/2 =3(n-1)。此时由29L的结论可得结论成立。显然以上归纳了每一种原命题的情况。原问题解是k次最多可以从 (3k-1)/2 个球里找出坏球.