- 最后登录
- 2009-2-2
- 在线时间
- 42 小时
- 阅读权限
- 40
- 注册时间
- 2006-3-2
- 积分
- 1609
- 帖子
- 266
- 精华
- 0
- UID
- 5208
- 性别
- 男
- 积分
- 1609
- 帖子
- 266
- 精华
- 0
- UID
- 5208
- 性别
- 男
|
<P>我们把讨论的问题归结为：<BR>若干小球质量相同，仅一个异常球质量不同。用电子秤称n次，最多肯定能从N个小球中找出这个异常球，并指出它的质量？<BR>指出异常球的质量，同时正常球的质量一般也就知道了。<BR>考虑的是最坏情况，要求出N与n的关系。<BR>记N=f(n)，求f。</P>
<P> </P>
<P>先证引理，最后结论就自然出来了。大前提都是“若干小球质量相同，仅一个异常球质量不同。要找出异常球，并指出它的质量”。</P>
<P> </P>
<P>P(n)：若知道正常球和异常球的质量，那么n次可以分辨2^n个小球。<BR>方法么，用对分法，略。</P>
<P>P(n)=2^n</P>
<P> </P>
<P>P'(n)：若知道正常球的质量，不知道异常球的质量，那么n次可以分辨(2^n)-1个小球。<BR>第一次称2^(n-1)个小球。<BR>若质量正常，那么问题归结到P'(n-1)；<BR>若质量异常，即异常球在这2^(n-1)个小球中，那么问题归结到P(n-1)。<BR>P'(1)=1。<BR>P'(n)=2^n-1。</P>
<P> </P>
<P>Q(n,m)：对于m组小球，异常球可能在任意一组；异常球在哪一组，都可确定正常球和异常球的质量。<BR>第一次，对每组小球取一半来称，就可以知道异常球在哪一组，在哪一半（上秤的或未称的），正常球和异常球的质量是多少。【注1】<BR>之后就归结到P(n-1)。<BR>Q(n,m)=m×2^n。</P>
<P> </P>
<P>Q'(n,m)：对于m组小球，异常球可能在任意一组；异常球在哪一组，都可确定正常球和异常球的质量，除了某个特殊组，只能确定正常球的质量。<BR>同样对每组小球取一半来称，就可以知道异常球在哪一组，在哪一半（上秤的或未称的），正常球和异常球的质量是多少；当然因为某特殊组的存在，若异常球确定在该特殊组，只能知道正常球的质量。<BR>对于其它组都归结到P(n-1)；对于特殊组归结到P'(n-1)。<BR>Q'(n,m)=m×2^n-1。</P>
<P> </P>
<P>【注1】Q系列命题未严格证明，每句话都只是“几乎”正确，应该说只是猜想。希望大家能给出严格证明。</P>
<P> </P>
<P>Q（系列）命题可以看作是P（系列）命题的扩充。</P>
<P> </P>
<P>回过来看原题目，4次称15个小球。</P>
<P> </P>
<P>与天平不同，电子秤得到的信息更隐蔽，要多个数据验证才能得到明确的结果。</P>
<P> </P>
<P>第一次，称a个球，得到质量aN，并不意味每个球的质量都是N。<BR>第二次，称b个球，得到质量bN'。<BR>若N=N'且a≠b，那么可以确定所有这些球都是正常的，质量为N；<BR>若N=N'且a=b，那么有可能所有这些球都是正常的，质量为N；也有可能两次称量中重复的球中有异常球，他们的质量还是不清楚，需要更多次的称量才能确定；（这个可以得到Q(n,2)命题。）<BR>若N≠N'，有三种可能：（1）aN=(a-1)x+y，bN'=bx；（2）aN=(a-1)x+y，bN'=(b-1)x+y；（3）aN=ax，bN'=(b-1)x+y。每种可能得到的(x,y)值都不一样。（这个可以得到Q(n,3)命题。）</P>
<P> </P>
<P>称2次，可以把球分成4组：0组是两次都没称的，1组是第一次称第二次没称的，2组是第一次没称第二次称的，3组是两次都称的。<BR>若2次称量，能确定称的都是正常球。根据P'(2)=3，0组最多3个球。<BR>若2次称量，能确定称的球中有异常球。根据Q(2,3)，1、2、3组每组都是4个球。<BR>问题是，这样2次都称了8个球（其中4个重复），结果要么是用了P'(2)，要么是用了Q'(2,2)，实际并未用到Q(2,3)。但这个也没关系，同样能解决问题，4次称15个小球。</P>
<P> </P>
<P>具体的称法如下：<BR>第一次，称1～8号球，得到质量8a。（质量以“球的数量”ד球的平均质量”的形式表示，有两个目的：一是为了减少之后的分数系数，方便计算；二是为了方便检验计算正确性，各种可能情况中，每个球的质量表示算式各系数之和均为1，n个球的质量表示算式各系数之和为n。）<BR>第二次，称5～12号球，得到质量8b。</P>
<P> </P>
<P>I）若b=a，意味着异常球只可能在5～8号球或13～15号球中。<BR>第三次称5、6、13、14号球，得到质量4c。<BR>i）若c=a，意味着称过的球都是正常球，15号球是异常球，第四次称15号球就知道它的质量也就是异常球的质量。<BR>ii）若c≠a，意味着异常球在5～8、13、14的球中。若异常球是5或6号球，则正常球质量为(1/4)(8a-4c)=2a-c【注3】，异常球质量为4c-3(2a-c)=7c-6a；若异常球是7或8号球，则正常球质量为c，异常球质量为8a-7c；若异常球是13或14号球，则正常球质量为a，异常球质量为4c-3a。注意到，三种情况下，正常球与异常球的质量是不相同的。<BR>第四次称5、7、13号球，得到质量D。<BR>D有6种可能：（1）异常球是5号球，则D=2(2a-c)+(7c-6a)=5c-2a；（2）异常球是6号球，则D=3(2a-c)=6a-3c；（3）异常球是7号球，则D=2c+(8a-7c)=8a-5c；（4）异常球是8号球，则D=3c；（5）异常球是13号球，则D=2a+(4c-3a)=4c-a；（6）异常球是14号球，则D=3a。6种可能情况，D的值都不一样，能完全确定异常球及其质量。<BR>（I是Q'(2,2)命题的实例。）</P>
<P> </P>
<P>II）若b≠a，意味着异常球在1～4号球或9～12号球中。<BR>若异常球在1～4号球中，则正常球的质量为b，异常球质量为8a-7b；若异常球在9～12号球中，则正常球的质量为a，异常球质量为8b-7a。注意到，两种情况下，正常球与异常球的质量是不相同的。<BR>第三次称1、2、9、10号球，得到质量C。<BR>C有4种可能：（1）异常球是1或2号球，则C=3b+(8a-7b)=8a-4b；（2）异常球是3或4号球，则C=4b；（3）异常球是9或10号球，则C=3a+(8b-7a)=8b-4a；（4）异常球是11或12号球，则C=4a。4种可能情况，C的值都不一样，能完全确定正常球和异常球的质量，并且知道异常球在哪2个球中间。第四次称其中1个球就能确定哪个是异常球了。<BR>（II是Q(2,2)命题的一个实例。）</P>
<P> </P>
<P>【注3】若c>2a，则这种情况就不存在，也就是异常球明显偏重时，更容易分辨。这个属于特殊情况，只会使问题更容易解决。同样的，对其它带减法的算式也可不考虑其正负。</P>
<P> </P>
<P>对于称n次来从(2^n)-1个球中找出异常球并指出它的质量（n≥4）的问题，用类似上述的方法。</P>
<P> </P>
<P>把(2^n)-1个球分成0～3号组，0号组有[2^(n-2)]-1个球，1～3号组都有2^(n-2)个球。<BR>第一次称1、3号组，得到质量A；第二次称2、3号组，得到质量B。<BR>若B=A，则意味着异常球在0、3号组中，应用Q'(n-2,2)命题。<BR>若B≠A，则意味着异常球在1、2号组中，应用Q(n-2,2)命题。</P>
<P> </P>
<P>问题1：是否有其它称法？能否称更多的球？<BR>回答：<BR>对于n=4的情况，这个是唯一的方法。<BR>对于n>4的情况，有其它的方法，但无法称更多的球。：<BR>任选k，2≤k≤n-2。<BR>把(2^n)-1个球分成0～[(2^k)-1]号组，0号组有[2^(n-k)]-1个球，1～3号组都有2^(n-k)个球。<BR>第i次称组编号二进制表示中倒数第i位为1的组的所有球，1≤i≤k。<BR>若k次得到的质量都相等，则应用Q'(n-k,2)命题；否则应用Q(n-k,(2^k)-1)命题。无法称更多的球。<BR>不过，应用Q(n-k,(2^k)-1)命题时计算太复杂（尽管有规律），取k=2是最简单的称法。</P>
<P> </P>
<P>问题2：对于n<4的情况，能称多少球呢？<BR>回答：<BR>n=1，特殊情况，认为唯一的球就是异常球，倒是仍满足(2^1)-1的公式。<BR>n=2，无法分辨2球或3球的情况，还是只能分辨1球的特殊情况。<BR>n=3，最多能分辨6球的情况。<BR></P>
<P>问题3：如果只要找出异常球，而不需要知道它的质量，那么可以秤多少个小球？</P>
<P>回答：</P>
<P>对P(n)命题，结论不变；对P'(n)命题，也可以做到称2^n个球；</P>
<P>同样的，对Q(m,n)命题，结论不变；对Q'(m,n)命题（它应用了P'(n)的结论），也可以做到称m×2^n个球。</P>
[ 本帖最后由 whitetiger 于 2008-4-21 09:49 编辑 ] |
|
IP卡
狗仔卡
发表于 2008-4-10 11:50:35
恢复卡
发表于 2008-4-10 12:06:26
