主题:【智慧一下】看看怎么做这道题阿 -- 坏坏哥
十三个球,外形都一样,其中十二个球重量一样,另外一个球重量跟这十二个球重量不一样,不过人手是无法感觉出来的,现在只给你一个天秤,只能测三次,把那个不一样的球挑选出来。
有办法没?
我认为是相当复杂滴,
——如果完全由自己想出这解决办法。
——如果还能清晰地表达这解决办法。
有的人说这个题很容易,BS 他/她!
将球编号1至13号,并用》表示天平称量左重右轻,《表示左轻右重,=表示左右一样重。
甲、第一次 若1234=5678
第二次 若123 = 9 10 11 得知 12或 13号次
第三次 很简单
第二次 若123 《 9 10 11 (因123为好球,故次品较重)
第三次 9=10 得知 11号次
第三次 9《10 得知 10号次
第三次 9》10 得知 9号次
第二次 若123 》 9 10 11 ...
乙、第一次 若1234<5678
天平两边一边取掉一球,一边取掉两球,假定左边取走12,右边取走8,并从已知好球中取一个补在左边,记为A;然后从两边各取一球(A球以外)的球进行交换,假定交换的是4号与6号,并进行称量,得如下结果:
第二次:若36A=457,次球在128号中,取18与两好球(AA)
第三次 18=AA 得知 2号坏
18》AA 得知 8号坏(若1号坏,应左边轻)
18《AA 得知 1号坏(类似上面)
第二次:若36A》457,此时357号为好球(否则不能左重右轻,见与第一次比较),再取46与两好球比较:
第三次:46=AA (不可能,因46必坏其一)
46》AA 得知 6号坏
46《AA 得知 4号坏
第二次:若36A《457,此时46号为好球(否则与第一次矛盾),取37号与两好球比较:
第三次:37=AA 得知5号坏
37《AA 得知3号坏
37》AA 得知7号坏
丙、第一次:若1234》4567,参考乙类情形。
有的是知道某一个球比其他的重或轻,有的是如本题根本不知轻重。
解决的关键,我认为,是把每个球先编号,再分组。然后怎么称重比较的过程就相对简单了。
如果没有编号这一步,每个球看起来都一样,便无从下手。
另外问题的问法也是有微妙区别的。这里问最多(或只能)称三次,如何称。
还有的是问最少要几次才能找出那个不同重量的球。答案是两次。
设想取两个球在天平两侧称,凑巧重量不一样。但是不知道是轻球比其他球轻还是重球比其他球重。于是要第二次称量。任意用第一次称量中轻或重球中的一个和另外的任意一个球称,还是轻或重的便是那唯一的另类。如果重量一样,则第一次称量时的另一个球为另类。
如果知道这个另类的球比别的重还是轻,3次可解了。
否则,问题很严重。
比如你的第一种情况,假设得知不同的球在12和13号里,可是你不知道这个不同的球到底是轻还是重,所以还是没法确定到底是谁。
参见:
Cover T.M. and Thomas J.A. "Elements of Information Theory"
第二章第13道习题.
这个题目难么......
这个问题我想:
天平两边每盘放5个球,余3个。如果天平平衡,那么这余下的3个球两步就可以分出不一样的球咯。
如果天平不平衡......
用天平每次称量会产生3个结果: "<","=",">".
故而三次称量产生3*3*3=27个结果.
{十三个球, 一个球重量跟其它十二个球重量不一样} 这共有26种可能性,因此找出"坏"球原则上不是不可行.
在设计称量的方案时,须要注意的是: 均衡地划分概率空间.
例子:
"天平两边每盘放5个球,余3个。"
如天平平衡, 那么余下的3个球一球为次, 共6种可能, 而两次称量给出3*3=9种可能性, 故而不是不可行. 但若天平不平衡, 那么就还剩10种可能性. 两次称量绝对无法决定何者为次. 所以此方案一开始就应被否决, 而不必再在这条路上花脑筋了.