《经典称球问题【学习资料】》由会员分享，可在线阅读，更多相关《经典称球问题【学习资料】（10页珍藏版）》请在金锄头文库上搜索。
1、我将首先致力于解决下面的问题：问题：已知 N 个球中有1个是坏的，但不知轻重，问用天平至少称多少次可以把它找出来，并判断轻重？在解决这个问题之后，将是此问题的一些推广，关于非随机应变策略，关于多臂天平，以及关于多个坏球等等。 我也说一句从一个最简单的问题开始问题：假设三个球中有一个不标准,且已知是重的,则可以称几次将非标准球找出来？个人企业举报垃圾信息举报我也说一句假设三个球中有一个不标准,且已知是重的,则可以称一次将非标准球找出来。方法是随便取两个来称，如果天平平衡，则第三个球是坏的，如果天平不平衡，则较重的那个球是坏的。那么，如果是9个球的话，又如何呢？假设9个球中有一个不标准,且已知是重
2、的,则可以称2次将非标准球找出来。方法是把9个球分成3组A,B,C，第一次称其中两组(A vs B)，如果天平平衡，说明坏球在C组，如果天平不平衡，则坏球在较重的那一组中，然后问题归结为3个球的情况 我也说一句假设3k个球中有一个不标准,且已知是重的,则可以称k次将非标准球找出来。或者说：【定理】假设 N 个球中有一个不标准,且已知是重的,则可以称log3(N)次将非标准球找出来。=找不到上取整符号，我用表示上取整，=好了，这是我们得到的第一个一般性的结论。为了严密起见，我将严格的证明它。我需要证明的是下面两条：1.N=3k+1时，称k次不能必然把坏球找出来。我也说一句 我也说一句 我也说一句
3、 我也说一句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|都
4、=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次不能必
5、然把坏球找出来。=或者说我们有这样一个原理：如果要从M种可能的情况中确定一种情况，又每次测量有a个结果，则最少需要测量loga(M) 次。当然实际需要的次数可能更多，因为你不能保证每次都得到“有用”的信息。但是 loga(M) 是所需次数的一个下界，我们把这个值称为【信息论下界】=回到4L的定理，我们有相对应的一个结论【定理】假设 N 个球中有一个不标准,且已知是轻的,则可以称log3(N)次将非标准球找出来。现在，在已知坏球轻重的情况下，我们得到了把坏球找出来的最少次数 我也说一句假设3k个球中有一个不标准,其中一部分已知不重,另一部分已知不轻,则可以称k次将非标准球找出来,并判定其轻重.假
6、设3k个球中有一个不标准,且这3k个球一部分已知不重,另一部分已知不轻,则可以称几次将非标准球找出来？=所谓某个球不重是指这个球或者是标准的，或者是坏的但比标准球轻=首先这个问题的信息论下界是 k 次，那么k次能把坏球找出来吗？ 我也说一句首先解决LS提出的问题：假设N=3k个球中有一个不标准,其中一部分已知不重,另一部分已知不轻,则可以称k次将非标准球找出来,并判定其轻重.（注意此处我没说N(3k-1)/2的话N=(3k+1)/2由信息论下界知称k次是不能将非标准球找出来,并判定其轻重的。） 我也说一句在归纳假设中，我假设命题对k-1成立，意思是对N=3(k-1)个球，只要满足命题条件，都可
7、以用k次将坏球找出来。或者说，3(k-1)分成两组，一组已知不重，一组已知不轻，（不论满不满足情形1）都可以用k次将坏球找出来。收起回复收起回复 我也说一句吧友58.61.56.*我看到13L的时候发现自己对不重不轻这两个概念理解不能k=1，N=3个球,共有四种情况(1) 全部不重 (2)全部不轻 (3) 两个球不重，一个球不轻 (4) 两个球不轻，一个球不重什么叫全部不重？什么叫全部不轻？ 我也说一句吧友58.61.56.*全部不重是指三个球全部不重于标准球？那就是坏球是轻球？那么两个不重，一个不轻又是指什么呢？有两个球不重于标准球，如果它们中有一个是坏球，那么坏球是轻球；如果不是，则坏球是
8、不轻的那个球，也就是重球。同样的，两个不轻，一个不重，则坏球分别是重球和轻球。是不是这样？ 我也说一句吧友58.61.56.*不知道为什么LZ要造出这两个概念来三个球，有一个是坏的，不是轻就是重。什么叫不轻？什么叫不重？这种题目总是用三分法来做的吧？分成三部分，两个一称，平的话在第三堆，不平的话则在这两堆中。然后继续判断。 我也说一句 我也说一句吧友58.61.56.*假设一次能一堆一堆的称，则球的总数目为3K情形的：均分三堆，称两次知道坏球在哪一堆，不可能更省（要包括最坏情形）令SI表示第I次得到的坏球那一堆的数目以及HI为此时已用的称量次数则HI=2I，SI=3(K-I)I=K时，HI=2
9、K,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
