稱球問題一般解法

1、稱球問題一般會(huì)有以下3種變形:1、n個(gè)球，其中有一個(gè)壞的，知道是輕還是重，用天平稱出壞球來。2、n個(gè)球，其中有一個(gè)壞的，不知是輕還是重，用天平稱出壞球來。3、n個(gè)球，其中有一個(gè)壞的，不知是輕還是重，用天平稱出壞球來，并告知壞 球是輕還是重。對(duì)于上面3種情況，稱量n次，最多可以在幾個(gè)球中找出壞球來？答案：分別為：3An, (3An -1)/2, (3An - 3)/2.稱法體現(xiàn)在下面的證明中：、天平稱重，有兩個(gè)托盤比較輕重，加上托盤外面，也就是每次稱重有3個(gè)結(jié) 果，就是In3/ln2比特信息。n個(gè)球要知道其中一個(gè)不同的球，如果知道那個(gè)不 同重量的球是輕還是重，找出來的話那就是n個(gè)結(jié)果中的一種，就

2、是有In(n)/ln2 比特信息，假設(shè)我們要稱k次，根據(jù)信息理論：k*ln3/ln2>=ln(n)/ln2,解得 k>=ln(n)/ln3這是得到下限，可以很輕易證明滿足條件的最小正整數(shù)k就是所求。比如稱3次知道輕重可以從3八3=27個(gè)球中找出不同的球出來。具體稱法就是：每次再待定的n個(gè)球中取(n+2)/3個(gè)球，放在天平左邊； (n+2)/3個(gè)球放在天平右邊。(注：x 表示不大于x的最大整數(shù)。)對(duì)于N(m)=(3Am-1)/2個(gè)小球，現(xiàn)在我們來尋求m次的解法。首先，對(duì)于m=2的情況，相當(dāng)于四個(gè)小球來稱兩次的情況，這個(gè)已經(jīng)討論過多次 了，也很簡(jiǎn)單，在此略去其次，若m <=k-1

3、時(shí)，假定對(duì)于N(k-1)=(3A(k-1)-1)/2個(gè)球的情況我們都有解法?，F(xiàn)在來考慮m=k的情況第一次稱取3A(k-1)-1個(gè)球放在天平天平兩端，則:如果平衡，獲得3A(k-1)-1個(gè)標(biāo)準(zhǔn)球，壞球在剩下的3A(k-1)+1/2 個(gè)中。由于3八(心1)-1>=3八(心1)+1/2，(k>=2),即已知的標(biāo)準(zhǔn)球數(shù)不小于未知球數(shù)；所以在以后的測(cè)量中就相當(dāng)于任意給定標(biāo)準(zhǔn)球的情況，由前面的引理 二可知對(duì)于3A(k-1)+1/2 的情況(k-1)次可解。如果不平衡，大的那方記做 A,小的那方記作B。標(biāo)準(zhǔn)球記做C.則現(xiàn)在我們有3A(k-1)-1/2 個(gè)A球和B球，有3A(k-1)+1/2 個(gè)C

4、球。第二次用3A(k-2)個(gè)A球加3A(k-2)-1/2個(gè)B球放左邊；3A(k-2)個(gè)C球加3A(k-2)-1/2 個(gè)A球放右邊。如果左邊大于右邊，則說明是在左邊的3A(k-2)個(gè)A球中質(zhì)量大的 為壞球；如果左邊等于右邊，則說明是在第二次稱時(shí)沒用的3A(k-2)個(gè)B球 中質(zhì)量輕的為壞球。以上兩種情況都可以再用三分法(k-2)次解決， 加上前兩次共k次解決。如果左邊小于右邊，則壞球在左邊的3A(k-2)-1/2 個(gè)B球中或在 右邊的同樣數(shù)目的A球中。此時(shí)的情況和第二次開始時(shí)類似(只不過是 k-1 變成k-2).用相同的辦法一直往下追溯到一個(gè)A球和一個(gè)B球一次區(qū)分的情 況，這時(shí)只需拿A球和標(biāo)準(zhǔn)球比

5、較以下就行了。因此在這種情況下也是可以最終用 k次解決的 由以上兩步加上數(shù)學(xué)歸納法知，對(duì)于 N(m)=(3Am-1)/2的情況，稱m次是可以稱 出來的。由這個(gè)解法加上前面所給出的上界 Nmax(m)v=(3Am-1)/2，知稱m次能解決的最 大的小球數(shù)Nmax(m)=(3Am-1)/2。有興趣的人可以驗(yàn)證一下 m=3,N=13的情況-該情況已經(jīng)被反復(fù)拿出來討論過 了。大家好，我們來繼續(xù)昨天的問題?，F(xiàn)在我要給出通解啦。為了簡(jiǎn)化下面的過程， 我們假設(shè)小球的個(gè)數(shù)正好是(3t-3)/2 。首先我們把小球分成數(shù)量相等的三組 AA|BiB|CiCn,其中n=(3t-1-1)/2 。 第一次使用天平的時(shí)候，

6、不妨把A組和B組分別放在天平左右盤。如果天平左低 右高，那么有可能因?yàn)樽筮卬個(gè)小球之一較重，也可能因?yàn)橛疫卬個(gè)小球之一較 輕。反過來也是一樣。這種時(shí)候，轉(zhuǎn)到下面的情況(1)處理。而天平平衡的時(shí)候， 則壞球一定在剩下n個(gè)小球中，(2)討論了這種問題?！厩闆r1】這時(shí)的條件是：已知AA中一個(gè)球較重，或者BBn中一個(gè)球較輕， 其中n=(3t-1-1)/2。我們把可以在C中任意拿出一個(gè)好球(C中的都是好球嘛) 放到B中去。然后由情況(3)討論接下來的處理方法。【情況2】這時(shí)的條件是：已知壞球GG中，且不知輕重關(guān)系，其中n=(3t-1 -1)/2 。 我們把C分作三組aiadb ibn|c iCm+i，其

7、中m=(3-2-1)/2。注意看啦，c組要 比a，b兩組多出一個(gè)。怎么？我們昨天不是說這種情況沒辦法完成嗎？但是， 我們現(xiàn)在多了一項(xiàng)武器-好球。對(duì)，我們可以從已經(jīng)判斷為一定是好球的A，B組中任意拿出一個(gè)好球，和 a一起放到天平左盤，把c組放到天平右盤，如果 天平左低右高，那么一定是a組中m個(gè)球較重或者c組重m+1個(gè)球較輕，反過來 也于這個(gè)類似，情況(3)正是討論這種問題的。如果平衡的話，說明b組的t_2m=(3 -1)/2個(gè)小球是問題小球，這不正好和我們當(dāng)前要討論的問題一樣嗎？所 以我們又回到了情況?！厩闆r3】這種情況最為復(fù)雜，我們知道的是 am中一個(gè)小球較重，或者C1 Cm+1中的一個(gè)小球較

8、輕，其中 m=(3_2_1)/2。另外，還有一個(gè)標(biāo)準(zhǔn)小球。我們把a(bǔ)分為a 1a s| B 1B s| 丫 1丫 s+1三組；把c分為& 1& s+1| E 1E s+1| Z 1Z s， 其中s=(3t-3_1)/2。把a(bǔ)&放再天平左盤，BE放在天平右盤。要是天平平衡， 說明要么丫組的s+1個(gè)小球較重，要么Z組的s個(gè)小球較輕，這恰恰是一個(gè)更 小規(guī)模的情況(3)。要是天平不平衡呢？以左低右高為例， 左盤是a£而右盤是 BE，這種情況不可能是由£較重引起的如果£中的球有壞球，它只會(huì)比好球輕。同樣也不會(huì)是B較輕引起的。所以，這個(gè)時(shí)候，要么是 a中

9、的S個(gè)球 之一較重，要么是E中的s+1個(gè)球之一較輕。這同樣是情況(3)。好了，到這里所有的情況都有了一個(gè)遞歸的算法。 可以把問題分解直到下面這些 情況：1. 使用一次天平，一個(gè)標(biāo)準(zhǔn)球，判斷一個(gè)壞球是輕還是重。2. 有兩個(gè)球，要么其中一個(gè)球較重，要么其中一個(gè)球較輕，仍然有標(biāo)準(zhǔn)球可 以利用，使用一次天平找到壞球。3. 三個(gè)球，要么是1號(hào)與2號(hào)球之一比較重，要么是3號(hào)球比較輕。使用一 次天平找到壞球。相信這三個(gè)問題相當(dāng)簡(jiǎn)單吧。什么，你不知道最后一種怎么做？呃，1號(hào)2號(hào)上天平，要是傾斜了，低的那邊是壞球；平衡的話好了，你可以嘗試使用五次天平解決120個(gè)球了。不過，一定要先找到一張非常 非常大的紙。另外

10、補(bǔ)充一點(diǎn)：對(duì)于(3t-1)/2個(gè)小球，如果另外給定一個(gè)標(biāo)準(zhǔn)球的話，就能以情 況(2)為入口，在t次內(nèi)找到壞球，并得知其偏重還是偏輕。而少了一個(gè)標(biāo)準(zhǔn)球， 就只能保證找到壞球，網(wǎng)路上的13球問題就是這樣的。稱球問題的一般解法稱球問題相信大家已經(jīng)很熟悉了， 并且已經(jīng)知道從 12個(gè)球中找岀壞球并判斷其輕重最多 只需要3次稱量。但如果把球數(shù)改變一下，比如說13個(gè)球，答案又是幾次呢？本文將對(duì)這一問題進(jìn)行“深入”分析。為了后面敘述方便，先在這里把一般化后的問題重復(fù)一下：有m( m> 3)個(gè)球，記為 q1、q2、qm，其中有且僅有一個(gè)壞球，其重量與其他的不 同，現(xiàn)使用無砝碼的天平進(jìn)行稱量，令n為稱量次數(shù)

11、，問：能確保找到壞球并指岀它與好球的輕重關(guān)系的n的最小值是多少？先來看理論上要多少次。每次稱量有左邊輕、平衡和右邊輕共 3種可能的情況，而壞球 的可能結(jié)果有q1輕、q1重、q2輕、q2重、qm輕、qm重等共2m種。因此，根據(jù)商農(nóng)的信息論，4個(gè)球,此問題的熵就是需要的稱量次數(shù)，又因?yàn)閚是整數(shù)，所以有:不過理論終歸是理論，直接拿到現(xiàn)實(shí)生活中往往行不通。一個(gè)很簡(jiǎn)單的情況:上面的公式說2次稱量就夠了。但你可以想想辦法，反正我是沒找到兩次解決問題的方案。q1輕和q2重，再稱一次就那,是理論錯(cuò)了嗎？唔，我可不敢懷疑商農(nóng)，我只敢懷疑我自己。來看看我們錯(cuò)在哪了 吧。對(duì)4個(gè)球的情況，第一次稱量只有兩個(gè)可選的方案

12、：方案1 : 5放左盤，q2放右盤。若不平 衡(由于對(duì)稱性，只分析左邊輕的情況，下同)，則可能的結(jié)果還剩 能找到壞球；若平衡，則可能的結(jié)果還剩 q3輕、q3重、q4輕和q4重4個(gè)，再套用一下商農(nóng)的定理， 此時(shí)還要稱 血?jiǎng)?chuàng)次。所以方案1被否決。方案2： q1、q2放左盤，q3、q4放右盤。此時(shí)天平肯定不會(huì)平衡，稱量后，可能的結(jié)果有qi輕、q2輕、q3重和q4重4個(gè)。同樣的道理，方案 2也難逃被否決的命運(yùn)。在4個(gè)球這么簡(jiǎn)單的情況下就撞得滿頭是包，未免讓人難以接受，總結(jié)一下經(jīng)驗(yàn)教訓(xùn)吧，把上面的分析歸納一下并推廣到一般情況，就是：整個(gè)稱量過程中，要達(dá)到目的，倒數(shù)第k次稱量前的可能結(jié)果數(shù) h，必須滿足條

13、件 h<3ko上面的得岀的結(jié)論雖然不能讓我們找到問題的答案，但卻有助于我們確定每次稱量的方案，特別是第一次如何做。假設(shè)我們計(jì)劃的稱量次數(shù)是n，第一次在左右兩盤中各放x個(gè)球，則保證下面兩個(gè)不等式同時(shí)成立是解決問題的必要條件：n i2（m-2x） <3 -（平衡時(shí)）2x<3 n-1 （不平衡時(shí)）把這兩個(gè)不等式稍加變換，就成了下面的樣子：2m-3< x <42注意到x是整數(shù)，3n-1是奇數(shù)，2m是偶數(shù)，所以上面的不等式等價(jià)于：2m-311-1于 i l"<42嚴(yán)-1顯然，在n 定的情況下， m越大，x的取值范圍越小，而當(dāng) x只能取值- 時(shí)，m繼續(xù)增 大，

14、就會(huì)導(dǎo)致n次稱量找到壞球的計(jì)劃破產(chǎn)。籍此，可以得岀在n定的情況下 m的取值范圍：m < 一1二。發(fā)現(xiàn)了嗎？現(xiàn)在 m的最大值正好比我們最初的結(jié)果少了1。同時(shí)此結(jié)果也與前面提到的4個(gè)球的實(shí)際情況相符。但分析了半天，我們只證明了m不在取值范圍內(nèi)時(shí)，n次稱量不能確保找到壞球。那m在取值范圍內(nèi)的時(shí)候，肯定能找到嗎？答案是肯定的，不過馬上證明它有點(diǎn)難，先來看兩個(gè)簡(jiǎn)單一點(diǎn)的命題。命題1:有A、B兩組球，球的個(gè)數(shù)分別為a、b，且0<b-a<1，已知這些球中有且僅有一個(gè)壞球，若它在 A組中，則比正常球輕，在 B組中則比正常球重。另有一個(gè)好球。先使用無 砝碼的天平稱量，令口二1°彷詆）

15、，則可以找到一個(gè)稱量方案，使得最多經(jīng)過n次稱量，就可以找到壞球（此時(shí)肯定能指岀它與好球的重量關(guān)系）。使用數(shù)學(xué)歸納法證明如下： 當(dāng)n=1時(shí)，a、b的取值可能有0, 1、1，1、1，2三組，由于還有一個(gè)已知的 好球，所以不難驗(yàn)證此時(shí)命題成立。 假設(shè)當(dāng)n=k時(shí)命題也成立。 當(dāng)n=k+1時(shí)。我們將 A、B兩組球分別盡量平均得分為三組，記為A1、A2、A3、B1、A1B2和B3。不影響一般性，假設(shè)這六組球按球數(shù)從少到多的排列次序也與前面的順序一致，且 有球al個(gè)。則第一次稱量時(shí)的稱量方案與每組球個(gè)數(shù)的對(duì)應(yīng)關(guān)系如下，其中需要注意的是：在帶藍(lán)色的兩種情況下，必有A1A2A3B1B2B3稱量方案a1a1a1a

16、1a1a1A1、B1放左盤；A2、B2放右盤a1a1a1a1a1a1+1A1、B1放左盤；A2、B2放右盤a1a1a1+1a1a1a1+1A1、B3放左盤；A3、B1放右盤a1a1a1+1a1a1+1a1+1A1、B2放左盤；A2、B3放右盤a1a1+1a1+1a1a1+1a1+1A2、B2放左盤；A3、B3放右盤a1a1+1a1+1a1+1a1+1a1+1A2、B2放左盤；A3、B3放右盤很明顯，不管結(jié)果是什么，第一次稱量之后，問題都能轉(zhuǎn)化為n=k時(shí)的情形。所以，命題 1是真前面已經(jīng)證明命題。n次稱量無法確保找到壞球并指岀其輕重關(guān)系。但如果此時(shí)也有一個(gè)已知的好球的話，答案就不一樣了，這時(shí)n次稱量就已經(jīng)足夠（命題 2）。仍使用數(shù)學(xué)歸納法。 當(dāng)n=2時(shí)，m=4,驗(yàn)證一下可知命題成立。 假設(shè)當(dāng)n=k時(shí)命題也成立。 當(dāng)n=k+1時(shí)。我們把這些球盡量平均的分成三組，則每組球的個(gè)數(shù)分別為:第一次稱量時(shí)，第一組和那個(gè)好球放左盤，第三組放右盤。若平衡，問題轉(zhuǎn)化為n=k時(shí)的情形，不平衡，問題轉(zhuǎn)化為命題1的情形。命題成立。有了前面兩個(gè)證明作基礎(chǔ)，最初的問題就很簡(jiǎn)單了，再次祭岀數(shù)據(jù)學(xué)歸納法。由于m<5時(shí)的情況有些特殊（考慮只有一個(gè)球或兩個(gè)球的情況），不能作為遞推得依據(jù)，所以我們從n=3，也就是m=5開始。 當(dāng)n=3時(shí)，m在5和12之間（13的情況已