?稱球問題相信大家已經(jīng)很熟悉了，并且已經(jīng)知道從12個球中找出壞球并判斷其輕重最多只需要3次稱量。但如果把球數(shù)改變一下，比如說13個球，答案又是幾次呢？本文將對這一問題進行“深入”分析。為了后面敘述方便，先在這里把一般化后的問題重復一下：
????有m（m≥3）個球，記為q1、q2、…、qm，其中有且僅有一個壞球，其重量與其他的不同，現(xiàn)使用無砝碼的天平進行稱量，令n為稱量次數(shù)，問：能確保找到壞球并指出它與好球的輕重關系的n的最小值是多少？
????先來看理論上要多少次。每次稱量有左邊輕、平衡和右邊輕共3種可能的情況，而壞球的可能結果有q1輕、q1重、q2輕、q2重、…、qm輕、qm重等共2m種。因此，根據(jù)商農(nóng)的信息論，此問題的熵就是需要的稱量次數(shù)，又因為n是整數(shù)，所以有：
????不過理論終歸是理論，直接拿到現(xiàn)實生活中往往行不通。一個很簡單的情況：4個球，上面的公式說2次稱量就夠了。但你可以想想辦法，反正我是沒找到兩次解決問題的方案。
????那，是理論錯了嗎？唔，我可不敢懷疑商農(nóng)，我只敢懷疑我自己。來看看我們錯在哪了吧。對4個球的情況，第一次稱量只有兩個可選的方案：方案1：q1放左盤，q2放右盤。若不平衡（由于對稱性，只分析左邊輕的情況，下同），則可能的結果還剩q1輕和q2重，再稱一次就能找到壞球；若平衡，則可能的結果還剩q3輕、q3重、q4輕和q4重4個，再套用一下商農(nóng)的定理，此時還要稱
次。所以方案1被否決。方案2：q1、q2放左盤，q3、q4放右盤。此時天平肯定不會平衡，稱量后，可能的結果有q1輕、q2輕、q3重和q4重4個。同樣的道理，方案2也難逃被否決的命運。
????在4個球這么簡單的情況下就撞得滿頭是包，未免讓人難以接受，總結一下經(jīng)驗教訓吧，把上面的分析歸納一下并推廣到一般情況，就是：整個稱量過程中，要達到目的，倒數(shù)第k次稱量前的可能結果數(shù)h，必須滿足條件h≤3k。
????上面的得出的結論雖然不能讓我們找到問題的答案，但卻有助于我們確定每次稱量的方案，特別是第一次如何做。假設我們計劃的稱量次數(shù)是n，第一次在左右兩盤中各放x個球，則保證下面兩個不等式同時成立是解決問題的必要條件：
????2(m-2x)≤3n-1? （平衡時）
??? 2x≤3n-1 （不平衡時）
把這兩個不等式稍加變換，就成了下面的樣子：
注意到x是整數(shù)，3n-1是奇數(shù)，2m是偶數(shù)，所以上面的不等式等價于：
顯然，在n一定的情況下，m越大，x的取值范圍越小，而當x只能取值
時，m繼續(xù)增大，就會導致n次稱量找到壞球的計劃破產(chǎn)。籍此，可以得出在n一定的情況下m的取值范圍：
。發(fā)現(xiàn)了嗎？現(xiàn)在m的最大值正好比我們最初的結果少了1。同時此結果也與前面提到的4個球的實際情況相符。
????但分析了半天，我們只證明了m不在取值范圍內(nèi)時，n次稱量不能確保找到壞球。那m在取值范圍內(nèi)的時候，肯定能找到嗎？答案是肯定的，不過馬上證明它有點難，先來看兩個簡單一點的命題。
????命題1：有A、B兩組球，球的個數(shù)分別為a、b，且0≤b-a≤1，已知這些球中有且僅有一個壞球，若它在A組中，則比正常球輕，在B組中則比正常球重。另有一個好球。先使用無砝碼的天平稱量，令
，則可以找到一個稱量方案，使得最多經(jīng)過n次稱量，就可以找到壞球（此時肯定能指出它與好球的重量關系）。
????使用數(shù)學歸納法證明如下：
????①當n=1時，a、b的取值可能有{0，1}、{1，1}、{1，2}三組，由于還有一個已知的好球，所以不難驗證此時命題成立。
????②假設當n=k時命題也成立。
????③當n=k+1時。我們將A、B兩組球分別盡量平均得分為三組，記為A1、A2、A3、B1、B2和B3。不影響一般性，假設這六組球按球數(shù)從少到多的排列次序也與前面的順序一致，且A1有球a1個。則第一次稱量時的稱量方案與每組球個數(shù)的對應關系如下，其中需要注意的是：在帶藍色的兩種情況下，必有
，否則就與命題的前提不符了。
|
A1
|
A2
|
A3
|
B1
|
B2
|
B3
|
稱量方案
|
|
a1
|
a1
|
a1
|
a1
|
a1
|
a1
|
A1、B1放左盤；A2、B2放右盤
|
|
a1
|
a1
|
a1
|
a1
|
a1
|
a1+1
|
A1、B1放左盤；A2、B2放右盤
|
|
a1
|
a1
|
a1+1
|
a1
|
a1
|
a1+1
|
A1、B3放左盤；A3、B1放右盤
|
|
a1
|
a1
|
a1+1
|
a1
|
a1+1
|
a1+1
|
A1、B2放左盤；A2、B3放右盤
|
|
a1
|
a1+1
|
a1+1
|
a1
|
a1+1
|
a1+1
|
A2、B2放左盤；A3、B3放右盤
|
|
a1
|
a1+1
|
a1+1
|
a1+1
|
a1+1
|
a1+1
|
A2、B2放左盤；A3、B3放右盤
|
很明顯，不管結果是什么，第一次稱量之后，問題都能轉化為n=k時的情形。所以，命題1是真命題。
??? 前面已經(jīng)證明
時，n次稱量無法確保找到壞球并指出其輕重關系。但如果此時也有一個已知的好球的話，答案就不一樣了，這時n次稱量就已經(jīng)足夠（命題2）。仍使用數(shù)學歸納法。
????①當n=2時，m=4，驗證一下可知命題成立。?
????②假設當n=k時命題也成立。?
????③當n=k+1時。我們把這些球盡量平均的分成三組，則每組球的個數(shù)分別為：
、、
。第一次稱量時，第一組和那個好球放左盤，第三組放右盤。若平衡，問題轉化為n=k時的情形，不平衡，問題轉化為命題1的情形。命題成立。
????有了前面兩個證明作基礎，最初的問題就很簡單了，再次祭出數(shù)據(jù)學歸納法。由于m<5時的情況有些特殊(考慮只有一個球或兩個球的情況)，不能作為遞推得依據(jù)，所以我們從n=3，也就是m=5開始。
????①當n=3時，m在5和12之間（13的情況已經(jīng)被排除在外），通過一一驗證可知命題成立。?
????②假設當n=k時命題也成立。?
????③當n=k+1時，找到一個滿足不等式的x，在天平左右兩盤中各放x個球。如果天平平衡，問題轉化為n=k時的情形或命題2中的情形；不平衡，則轉化為命題1的情形。命題成立。
????綜上所述，稱球問題的完整答案是：當球數(shù)時，n次稱量時就能確保找到壞球，并指出它與好球的輕重關系；當球數(shù)時，n次稱量只能確保找到壞球，而無法指出它與好球的輕重關系。要想指出輕重關系，就可能需要多進行一次稱量。但如果此時再有一個好球，就又可以把這次稱量省掉了。
from: http://blog.vckbase.com/localvar/archive/2005/07/17/9717.aspx