?

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

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

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

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

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

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

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

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

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

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

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

顯然，在n一定的情況下，m越大，x的取值范圍越小，而當(dāng)x只能取值時(shí)，m繼續(xù)增大，就會(huì)導(dǎo)致n次稱量找到壞球的計(jì)劃破產(chǎn)。籍此，可以得出在n一定的情況下m的取值范圍：。發(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è)簡單一點(diǎn)的命題。

????命題1：有A、B兩組球，球的個(gè)數(shù)分別為a、b，且0≤b-a≤1，已知這些球中有且僅有一個(gè)壞球，若它在A組中，則比正常球輕，在B組中則比正常球重。另有一個(gè)好球。先使用無砝碼的天平稱量，令，則可以找到一個(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、B2和B3。不影響一般性，假設(shè)這六組球按球數(shù)從少到多的排列次序也與前面的順序一致，且A1有球a1個(gè)。則第一次稱量時(shí)的稱量方案與每組球個(gè)數(shù)的對應(yīng)關(guān)系如下，其中需要注意的是：在帶藍(lán)色的兩種情況下，必有，否則就與命題的前提不符了。

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放右盤

很明顯，不管結(jié)果是什么，第一次稱量之后，問題都能轉(zhuǎn)化為n=k時(shí)的情形。所以，命題1是真命題。

??? 前面已經(jīng)證明時(shí)，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ǔ)，最初的問題就很簡單了，再次祭出數(shù)據(jù)學(xué)歸納法。由于m<5時(shí)的情況有些特殊(考慮只有一個(gè)球或兩個(gè)球的情況)，不能作為遞推得依據(jù)，所以我們從n=3，也就是m=5開始。

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

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