魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: geslon

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

积分
1393
帖子
228
精华
0
UID
142
性别
发表于 2008-4-10 11:50:35 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2008-4-10 12:06:26 |显示全部楼层
原帖由 <I>hw294</I> 于 2008-4-10 11:48 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&amp;pid=110337&amp;ptid=6973" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
<P>这样的话5号球和13号球是异常球时从结果上看将无法区分<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12"> </P>
<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp; 能区分的<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12">。咱俩的方法是一样的!请你再仔细考虑一下!<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12">&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

积分
1393
帖子
228
精华
0
UID
142
性别
发表于 2008-4-10 12:16:03 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

使用道具 举报

Rank: 2

积分
312
帖子
288
精华
0
UID
21799
性别
发表于 2008-4-10 12:21:52 |显示全部楼层
值得去探讨的一个问题呀

使用道具 举报

Rank: 8Rank: 8

积分
4787
帖子
1876
精华
12
UID
93
性别

魔方理论探索者 十年元老

发表于 2008-4-10 13:58:08 |显示全部楼层
&nbsp;&nbsp;&nbsp; <BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; 嗯,原来误以为<BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp; 5 号是 异常球 时结果分别是 7x+y,7x+y,3x+y,3x+y<BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp; 13 号是 异常球 时结果分别是 8x,8x,3x+y,3x+y<BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; 就能区分“异常球”! 晕了,还是 hw294 心细!<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28"> 不知道咱们的解答还有问题吗?<BR>这就全权交给 hw294 了!<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/handshake.gif" border=0 smilieid="17">&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 这个问题如果解决了,请大家继续思考如何解决: <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 如果<FONT color=blue><STRONG>不</STRONG></FONT>考虑求 异常球 的重量,如何确定出 15 个以上球中的 异常球&nbsp; ! <BR>那么此时<FONT color=blue><STRONG>最多</STRONG></FONT>可以确定 多少 个小球中有 异常球&nbsp; !<BR>&nbsp; <BR>&nbsp; <BR>&nbsp;&nbsp;&nbsp; <BR>&nbsp;&nbsp;&nbsp;
~~ 宇宙在旋转运动 ~~ 魔方在循环变换 ~~

使用道具 举报

Rank: 1

积分
72
帖子
48
精华
1
UID
23922
性别
保密
发表于 2008-4-10 23:50:02 |显示全部楼层
大家讨论的有点意思了,再完善一下就好了。如果不要求知道重量,16球是极限。

使用道具 举报

Rank: 4

积分
1609
帖子
266
精华
0
UID
5208
性别
发表于 2008-4-15 08:17:06 |显示全部楼层
<P>我们把讨论的问题归结为:<BR>若干小球质量相同,仅一个异常球质量不同。用电子秤称n次,最多肯定能从N个小球中找出这个异常球,并指出它的质量?<BR>指出异常球的质量,同时正常球的质量一般也就知道了。<BR>考虑的是最坏情况,要求出N与n的关系。<BR>记N=f(n),求f。</P>
<P>&nbsp;</P>
<P>先证引理,最后结论就自然出来了。大前提都是“若干小球质量相同,仅一个异常球质量不同。要找出异常球,并指出它的质量”。</P>
<P>&nbsp;</P>
<P>P(n):若知道正常球和异常球的质量,那么n次可以分辨2^n个小球。<BR>方法么,用对分法,略。</P>
<P>P(n)=2^n</P>
<P>&nbsp;</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>&nbsp;</P>
<P>Q(n,m):对于m组小球,异常球可能在任意一组;异常球在哪一组,都可确定正常球和异常球的质量。<BR>第一次,对每组小球取一半来称,就可以知道异常球在哪一组,在哪一半(上秤的或未称的),正常球和异常球的质量是多少。【注1】<BR>之后就归结到P(n-1)。<BR>Q(n,m)=m×2^n。</P>
<P>&nbsp;</P>
<P>Q'(n,m):对于m组小球,异常球可能在任意一组;异常球在哪一组,都可确定正常球和异常球的质量,除了某个特殊组,只能确定正常球的质量。<BR>同样对每组小球取一半来称,就可以知道异常球在哪一组,在哪一半(上秤的或未称的),正常球和异常球的质量是多少;当然因为某特殊组的存在,若异常球确定在该特殊组,只能知道正常球的质量。<BR>对于其它组都归结到P(n-1);对于特殊组归结到P'(n-1)。<BR>Q'(n,m)=m×2^n-1。</P>
<P>&nbsp;</P>
<P>【注1】Q系列命题未严格证明,每句话都只是“几乎”正确,应该说只是猜想。希望大家能给出严格证明。</P>
<P>&nbsp;</P>
<P>Q(系列)命题可以看作是P(系列)命题的扩充。</P>
<P>&nbsp;</P>
<P>回过来看原题目,4次称15个小球。</P>
<P>&nbsp;</P>
<P>与天平不同,电子秤得到的信息更隐蔽,要多个数据验证才能得到明确的结果。</P>
<P>&nbsp;</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>&nbsp;</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>&nbsp;</P>
<P>具体的称法如下:<BR>第一次,称1~8号球,得到质量8a。(质量以“球的数量”ד球的平均质量”的形式表示,有两个目的:一是为了减少之后的分数系数,方便计算;二是为了方便检验计算正确性,各种可能情况中,每个球的质量表示算式各系数之和均为1,n个球的质量表示算式各系数之和为n。)<BR>第二次,称5~12号球,得到质量8b。</P>
<P>&nbsp;</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>&nbsp;</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>&nbsp;</P>
<P>【注3】若c&gt;2a,则这种情况就不存在,也就是异常球明显偏重时,更容易分辨。这个属于特殊情况,只会使问题更容易解决。同样的,对其它带减法的算式也可不考虑其正负。</P>
<P>&nbsp;</P>
<P>对于称n次来从(2^n)-1个球中找出异常球并指出它的质量(n≥4)的问题,用类似上述的方法。</P>
<P>&nbsp;</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>&nbsp;</P>
<P>问题1:是否有其它称法?能否称更多的球?<BR>回答:<BR>对于n=4的情况,这个是唯一的方法。<BR>对于n&gt;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>&nbsp;</P>
<P>问题2:对于n&lt;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 编辑 ]

使用道具 举报

Rank: 1

积分
26
帖子
19
精华
0
UID
27758
性别
保密
发表于 2008-4-17 22:01:55 |显示全部楼层
第一次进入这个板块,
虽然我魔方速度不行,但这种题目我最擅长...喜喜...
这题目我做过,
先分别取5个球,让后放天平两端称,如果平衡则证明重的那个球不在这称过10个里头,
如果天平不平衡则说明那颗特别的球就在重的那端了,
接下来......
现在已经用了一次机会了,.现在把目标控制在5个球之中了,
这下方法多了,反正跟上面的想法是一样的了....
而且一共只需要3次..
4.7开始学习魔方    学习ing~~ 4.16最快78秒,平均102有提高就修改资料,嘻嘻~

使用道具 举报

Rank: 1

积分
26
帖子
19
精华
0
UID
27758
性别
保密
发表于 2008-4-17 22:04:02 |显示全部楼层
看错题目了,
是电子称啊.....
不过思路还是一样的哦哦哦哦....
这下确实需要4次了!~
4.7开始学习魔方    学习ing~~ 4.16最快78秒,平均102有提高就修改资料,嘻嘻~

使用道具 举报

红魔

sub18

Rank: 4

积分
2291
帖子
2047
精华
1
UID
18627
性别

两年元老 国家(地区)纪录(NR)

发表于 2008-4-17 22:11:28 |显示全部楼层
我见过这种题目的一个公式,给出n(小球的数量),可知道至少称几次

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-28 22:21

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部