楼主: geslon

geslon系列难题之二：电子秤称小球问题 [复制链接]

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

1^#

发表于 2008-4-15 08:17:06 |显示全部楼层

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

[ 本帖最后由 whitetiger 于 2008-4-21 09:49 编辑 ]

使用道具举报

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

2^#

发表于 2008-4-21 09:51:39 |显示全部楼层

原帖由 geslon 于 2008-4-20 23:27 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=116645&ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A>
<DIV class=t_msgfont id=postmessage_116645>
<CITE>对于本人出的这道题，好多网友都回答得很棒，谢谢。不过一直没有看到符合我的完整回答的答案。</CITE>
<CITE></CITE> 
<CITE>特别感谢whitetiger在37楼的详细解答和深入思考。你的答案，虽不中，亦不远矣~~</CITE>
<CITE></CITE> 
<CITE>比如，在情况1）里，你觉得不可能是7或者8号球有问题么？可你根本没有考虑它们俩。</CITE></DIV>

是I），不是1）。
确实没提，因为我写的时候漏掉了，现在已经改正了。
 
主要把精力集中在前面那些命题的考虑上了，对于具体问题的解决只是操作层面的问题，通过前面命题的描述应该能解决。

使用道具举报

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

3^#

发表于 2008-4-24 08:14:29 |显示全部楼层

原帖由 魔方小厦 于 2008-4-23 18:35 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=118231&ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 电子称是天平的吗???

当然不是天平。
电子秤，是指能称出重量（数值）的秤。

使用道具举报

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

4^#

发表于 2008-5-13 12:22:05 |显示全部楼层

原帖由 sthforever 于 2008-5-12 20:07 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=132452&ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 我想了一个通用的解法，不知有没有问题。   假设有N个球，其中有一个球质量与其他不同。设不同的球质量为q，而其他的球质量为p。   为方便，将N写成二进制数的位数记为n。将这N个球从0到N-1编号，并把 ...

是18#的改进。
 
该方法应该确实可行，也是完全可以证明的。（尽管他说没完整的证明。）

使用道具举报

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

5^#

发表于 2008-5-15 12:24:40 |显示全部楼层

原帖由 xingwenyong 于 2008-5-14 10:20 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=133372&ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 你们把这个题想复杂了吧，n次可以从2的n次方减一个小球中称出异常球，像这个题16个球的话，点背的话，必须用到5次称出来

是你把问题想简单了，或者说还没理解题目。
 
n=2的情况，你怎么能只称2次，从3个球中找出异常球？（用电子秤）

使用道具举报

whitetiger

红魔

Rank: 4

积分: 1609
帖子: 266
精华: 0
UID: 5208
性别: 男

6^#

发表于 2008-5-15 12:26:08 |显示全部楼层

原帖由 xingwenyong 于 2008-5-14 10:21 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=133373&ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 如果有刻度的话，也就是知道异常球是大了还是小了的话，可以称出2的n次方，就不必减一了

怎么能称1次，从2个球中找出异常球？
 
注意，题目是用电子秤，告诉你异常球是轻是重都没用！

使用道具举报

返回列表

		自动登录	找回密码
密码			注册