?

??? 稱球問題相信大家已經很熟悉了，并且已經知道從12個球中找出壞球并判斷其輕重最多只需要3次稱量。但如果把球數改變一下，比如說13個球，答案又是幾次呢？本文將對這一問題進行“深入”分析。為了后面敘述方便，先在這里把一般化后的問題重復一下：

????有m（m≥3）個球，記為q₁、q₂、…、q_m，其中有且僅有一個壞球，其重量與其他的不同，現使用無砝碼的天平進行稱量，令n為稱量次數，問：能確保找到壞球并指出它與好球的輕重關系的n的最小值是多少？

????先來看理論上要多少次。每次稱量有左邊輕、平衡和右邊輕共3種可能的情況，而壞球的可能結果有q₁輕、q₁重、q₂輕、q₂重、…、q_m輕、q_m重等共2m種。因此，根據商農的信息論，此問題的熵就是需要的稱量次數，又因為n是整數，所以有：

????不過理論終歸是理論，直接拿到現實生活中往往行不通。一個很簡單的情況：4個球，上面的公式說2次稱量就夠了。但你可以想想辦法，反正我是沒找到兩次解決問題的方案。

????那，是理論錯了嗎？唔，我可不敢懷疑商農，我只敢懷疑我自己。來看看我們錯在哪了吧。對4個球的情況，第一次稱量只有兩個可選的方案：方案1：q₁放左盤，q₂放右盤。若不平衡（由于對稱性，只分析左邊輕的情況，下同），則可能的結果還剩q₁輕和q₂重，再稱一次就能找到壞球；若平衡，則可能的結果還剩q₃輕、q₃重、q₄輕和q₄重4個，再套用一下商農的定理，此時還要稱次。所以方案1被否決。方案2：q₁、q₂放左盤，q₃、q₄放右盤。此時天平肯定不會平衡，稱量后，可能的結果有q₁輕、q₂輕、q₃重和q₄重4個。同樣的道理，方案2也難逃被否決的命運。

????在4個球這么簡單的情況下就撞得滿頭是包，未免讓人難以接受，總結一下經驗教訓吧，把上面的分析歸納一下并推廣到一般情況，就是：整個稱量過程中，要達到目的，倒數第k次稱量前的可能結果數h，必須滿足條件h≤3^k。

????上面的得出的結論雖然不能讓我們找到問題的答案，但卻有助于我們確定每次稱量的方案，特別是第一次如何做。假設我們計劃的稱量次數是n，第一次在左右兩盤中各放x個球，則保證下面兩個不等式同時成立是解決問題的必要條件：

????2(m-2x)≤3^n-1? （平衡時）

??? 2x≤3^n-1 （不平衡時）

把這兩個不等式稍加變換，就成了下面的樣子：

注意到x是整數，3n-1是奇數，2m是偶數，所以上面的不等式等價于：

顯然，在n一定的情況下，m越大，x的取值范圍越小，而當x只能取值時，m繼續增大，就會導致n次稱量找到壞球的計劃破產。籍此，可以得出在n一定的情況下m的取值范圍：。發現了嗎？現在m的最大值正好比我們最初的結果少了1。同時此結果也與前面提到的4個球的實際情況相符。

????但分析了半天，我們只證明了m不在取值范圍內時，n次稱量不能確保找到壞球。那m在取值范圍內的時候，肯定能找到嗎？答案是肯定的，不過馬上證明它有點難，先來看兩個簡單一點的命題。

????命題1：有A、B兩組球，球的個數分別為a、b，且0≤b-a≤1，已知這些球中有且僅有一個壞球，若它在A組中，則比正常球輕，在B組中則比正常球重。另有一個好球。先使用無砝碼的天平稱量，令，則可以找到一個稱量方案，使得最多經過n次稱量，就可以找到壞球（此時肯定能指出它與好球的重量關系）。

????使用數學歸納法證明如下：

????①當n=1時，a、b的取值可能有{0，1}、{1，1}、{1，2}三組，由于還有一個已知的好球，所以不難驗證此時命題成立。
????②假設當n=k時命題也成立。
????③當n=k+1時。我們將A、B兩組球分別盡量平均得分為三組，記為A1、A2、A3、B1、B2和B3。不影響一般性，假設這六組球按球數從少到多的排列次序也與前面的順序一致，且A1有球a1個。則第一次稱量時的稱量方案與每組球個數的對應關系如下，其中需要注意的是：在帶藍色的兩種情況下，必有，否則就與命題的前提不符了。

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是真命題。

??? 前面已經證明時，n次稱量無法確保找到壞球并指出其輕重關系。但如果此時也有一個已知的好球的話，答案就不一樣了，這時n次稱量就已經足夠（命題2）。仍使用數學歸納法。

????①當n=2時，m=4，驗證一下可知命題成立。?
????②假設當n=k時命題也成立。?
????③當n=k+1時。我們把這些球盡量平均的分成三組，則每組球的個數分別為：、、。第一次稱量時，第一組和那個好球放左盤，第三組放右盤。若平衡，問題轉化為n=k時的情形，不平衡，問題轉化為命題1的情形。命題成立。

????有了前面兩個證明作基礎，最初的問題就很簡單了，再次祭出數據學歸納法。由于m<5時的情況有些特殊(考慮只有一個球或兩個球的情況)，不能作為遞推得依據，所以我們從n=3，也就是m=5開始。

????①當n=3時，m在5和12之間（13的情況已經被排除在外），通過一一驗證可知命題成立。?
????②假設當n=k時命題也成立。?
????③當n=k+1時，找到一個滿足不等式的x，在天平左右兩盤中各放x個球。如果天平平衡，問題轉化為n=k時的情形或命題2中的情形；不平衡，則轉化為命題1的情形。命題成立。

????綜上所述，稱球問題的完整答案是：當球數時，n次稱量時就能確保找到壞球，并指出它與好球的輕重關系；當球數時，n次稱量只能確保找到壞球，而無法指出它與好球的輕重關系。要想指出輕重關系，就可能需要多進行一次稱量。但如果此時再有一個好球，就又可以把這次稱量省掉了。