资源描述：
《经典称球问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、我将首先致力于解决下面的问题：问题：已知N个球中有1个是坏的，但不知轻重，问用天平至少称多少次可以把它找出来，并判断轻重？在解决这个问题之后，将是此问题的一些推广，关于非随机应变策略，关于多臂天平，以及关于多个坏球等等。·我也说一句 从一个最简单的问题开始问题：假设三个球中有一个不标准,且已知是重的,则可以称几次将非标准球找出来？个人企业举报垃圾信息举报我也说一句 假设三个球中有一个不标准,且已知是重的,则可以称一次将非标准球找出来。方法是随便取两个来称，如果天平平衡，则第三个球是坏的，如果天平不平衡，则
2、较重的那个球是坏的。那么，如果是9个球的话，又如何呢？假设9个球中有一个不标准,且已知是重的,则可以称2次将非标准球找出来。方法是把9个球分成3组A,B,C，第一次称其中两组(AvsB)，如果天平平衡，说明坏球在C组，如果天平不平衡，则坏球在较重的那一组中，然后问题归结为3个球的情况·我也说一句 假设3^k个球中有一个不标准,且已知是重的,则可以称k次将非标准球找出来。或者说：【定理】假设N个球中有一个不标准,且已知是重的,则可以称{log3(N)}次将非标准球找出来。======找不到上取整符号，我用{
3、}表示上取整，=====好了，这是我们得到的第一个一般性的结论。为了严密起见，我将严格的证明它。我需要证明的是下面两条：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
4、=1时不用说了N=2时，有两个球A,B，则称AvsB，较重的那个是坏的，一次就可以把坏球找出来N=3时,见3L。也是一次就可以把坏球找出来。(2)假设对k-1命题成立，即N<=3^(k-1)时，可以称k-1次把坏球找出来。当N<=3^k时，首先将N个球平均分成A,B,C3份(此处“平均”是指每两份之间相差不超过1个)容易知道，
5、A
6、,
7、B
8、,
9、C
10、都<=3^(k-1)，并且其中有两组球个数相等（有可能三组球个数都相等）我们取出两组个数相等的球，不妨设为A,B第一次称AvsB如果天平平衡，说明坏球在C组中，
11、如果天平不平衡，说明坏球在A,B中较重的那一组中总之，我们把坏球限制在A,B,C中的一组当中由于每一组球的个数都<=3^(k-1),由归纳假设，我们可以用k-1次从A(或BC)中将坏球找出来因此我们可以用k次从N<=3^k个球中将坏球找出来。证毕2.N>=3^k+1时，称k次不能必然把坏球找出来。这个涉及到信息论，简单来说就是一共有3^k+1种可能的结果，每一次称量可以从3组（互不相容的）信息中选出一种因此k次称量最多可以从3^k种不同的结果中选出一种所以N>=3^k+1时，称k次不能必然把坏球找出来。=
12、=============================================或者说我们有这样一个原理：如果要从M种可能的情况中确定一种情况，又每次测量有a个结果，则最少需要测量{loga(M)}次。当然实际需要的次数可能更多，因为你不能保证每次都得到“有用”的信息。但是{loga(M)}是所需次数的一个下界，我们把这个值称为【信息论下界】===================================================回到4L的定理，我们有相对应的一个结论【定理】假设N个
13、球中有一个不标准,且已知是轻的,则可以称{log3(N)}次将非标准球找出来。现在，在已知坏球轻重的情况下，我们得到了把坏球找出来的最少次数·我也说一句 假设3k个球中有一个不标准,其中一部分已知不重,另一部分已知不轻,则可以称k次将非标准球找出来,并判定其轻重.假设3^k个球中有一个不标准,且这3^k个球一部分已知不重,另一部分已知不轻,则可以称几次将非标准球找出来？=====所谓某个球不重是指这个球或者是标准的，或者是坏的但比标准球轻=====首先这个问题的信息论下界是k次，那么k次能把坏球找出来吗
14、？·我也说一句 首先解决LS提出的问题：假设N=3^k个球中有一个不标准,其中一部分已知不重,另一部分已知不轻,则可以称k次将非标准球找出来,并判定其轻重.（注意此处我没说N<=3^k,因为有一种情况——N=2,一个球已知不轻，另一个已知不重——称多少次都不能找出坏球的）现在证明，对k归纳。k=0不用多说。k=1，N=3个球,共有四种情况(1)全部不重(2)全部不轻(3)两个球不重，一个球不轻(4)两个球不轻，一个球不重对于(
