最近有個(gè)小朋友問了我一個(gè)問題：

“在12個(gè)小球里有一個(gè)次品，重量與其他11個(gè)球不同。用一個(gè)沒有砝碼的天平，最少稱幾次，才能保證找到那個(gè)次品，并且區(qū)分出次品是輕還是重呢？”

這個(gè)問題看似簡單，做起來還真不容易。

一、9個(gè)球，已知次品輕重

我們首先來研究一個(gè)簡化版本，這是在小學(xué)五年級課本上的一道題：

“已知有9個(gè)球中有一個(gè)次品球比其他球更重，用天平至少稱幾次才能保證找到那個(gè)次品球？”

相比于標(biāo)準(zhǔn)問題，簡化版本多了一個(gè)條件——我們知道次品球比其他球更重。這樣問題就簡單多了，你還記得答案嗎？

也許有人說：我可以用二分法，先把球均分成兩堆，上天平比較，找到重的一堆，次品就在這里。再把重的一堆均分成兩堆，上天平比較…這樣，每次就能把球去掉一半，就能最快找到次品啦！

其實(shí)，二分法并不是步驟最少的。因?yàn)樘炱椒Q一次，有三種狀態(tài)：左邊重、右邊重或者平衡。二分法只利用了其中的兩種情況。我們應(yīng)該在每一次測量的時(shí)候充分利用天平的特點(diǎn)，減小問題的不確定性，我們大約可以把它稱為“三分法”。

以9球?yàn)槔菏紫葘?個(gè)球編號1-9，然后把它們分成均勻的三堆：1、2、3號一堆、4、5、6號一堆、7、8、9號一堆。

第一次測量時(shí)：把1、2、3號球放在天平左盤，4、5、6號球放在天平右盤，7、8、9號球放在一邊。

因?yàn)榇纹非蚋?，所以如果天平向左邊傾斜，就說明次品在1、2、3號中；如果向右邊傾斜，說明次品在4、5、6號中；如果平衡，說明次品在7、8、9號中。

我們發(fā)現(xiàn)：無論出現(xiàn)哪一種結(jié)果，我都把“從9個(gè)球中找次品”的問題轉(zhuǎn)化成“從3個(gè)球中找次品”的問題，不確定性大大縮小了。

第二次測量時(shí)，假設(shè)次品在1、2、3號球中，我們就需要再把這三個(gè)球再平均分成三份，每一份就只有一個(gè)球了。然后，把1號球放在天平左端，2號球放在天平右端，3號球放在一邊，進(jìn)行第二次測量。

如果天平向左邊傾斜，1號球是次品；天平向右側(cè)傾斜，2號是次品；天平平衡，3號是次品。第二次測量，我們把次品的可能范圍從3個(gè)球壓縮到1個(gè)球。

利用每次均分成3份的方法，我們只需要2次測量，就能從9個(gè)球中找到那個(gè)較重的次品了。

二、N個(gè)球，已知次品輕重

根據(jù)以上的例子，我們發(fā)現(xiàn)：如果在已知次品輕重的前提下，想最快找到次品，應(yīng)該每次將剩余的球均分成三堆，通過天平測量，理想情況下可以把次品的可能性壓縮到其中的1/3。

假如有N個(gè)球，每測一次，次品可能性就被壓縮到1/3，測量k次后，次品的可能性小于等于1，我們就保證找到了這個(gè)次品。所以，需要滿足的條件是：

反過來，測量k次，最多能從N個(gè)球中找到一個(gè)已知輕重的次品球，N必須滿足條件：

我們可以列一個(gè)表格，幫助大家快速尋找答案。

*注意：如果球的數(shù)量不能均分，只需要把不相等的數(shù)放在天平下即可。例如有26個(gè)球，可以分成9-9-8三堆，9和9上天平，8球在下方，結(jié)果不變。

消除不確定性，其實(shí)是信息熵的作用。大家是否玩過一個(gè)游戲，叫做我想你猜。我心里想個(gè)人物，你問我問題，我回答是或者否。例如：

? ? 問：是中國的嗎？

????答：是

????問：是武將嗎？

????答：是

????問：是李云龍嗎？

????答：是！

每一次是或者否，都能消除一半的不確定度。如果我只認(rèn)識1024個(gè)人，那么你最多問我10個(gè)問題，就能猜到我心里想的是誰。同樣，在天平稱小球的問題中，因?yàn)槊看斡腥N可能結(jié)果，所以每次消除的不確定性更多。如果問題有是、否、不確定三種回答，理論上10個(gè)問題，可以從59049個(gè)人物中找到答案。

三、6個(gè)球，不知次品輕重

如果我們只知道次品重量不同，但是不知道是輕是重。至少需要測量多少次，才能保證找到次品，并且測出次品的輕重呢？

顯然，如果不知道次品的輕重，那么問題的不確定性就多了。我們還是從簡單的情況開始：
有6個(gè)球，從中找到一個(gè)次品，次品的可能性共有12種：

1號球輕、2號球輕、3號球輕、4號球輕、5號球輕、6號球輕；

1號球重、2號球重、3號球重、4號球重、5號球重、6號球重。

第一次測量：將六個(gè)球中1、2號放在天平左邊，3、4號放在天平右邊，5、6號放在旁邊。這樣分配的原則與之前相同：盡量充分利用平衡的三種可能結(jié)果。

測量結(jié)果和可能性我列在下表：

這樣，無論獲得什么結(jié)果，第一次測量后，我都把12種可能壓縮為4種了。

2.1 若第一次測量，天平不平衡。

如果第一次測量天平左側(cè)重，我們就知道壞球在1、2、3、4之間，而5和6是好球。第二次測量可以使用這樣的策略：1號和3號球放在天平左側(cè)，4號球和一個(gè)好球（如5號球）放在天平右側(cè)。

根據(jù)之間已經(jīng)獲得的信息，容易分析出這時(shí)三種結(jié)果對應(yīng)的情況：

這樣，我們就把四種情況又分為2-1-1三類了。

如果第一次測量，天平右側(cè)重，方法是類似的。

2.2 若第一次測量，天平平衡

如果第一次測量天平平衡，我們知道壞球在5、6號球中，對應(yīng)四種可能。此時(shí)我們可以用5號球與一個(gè)好球（比如1號）比較：

結(jié)果如下：

按照這樣的方法，在第二次測量結(jié)束后，我們把四種情況壓縮到1種或者2種情況之中了。
如果只剩下1種情況，那么我們就找到了次品，并且知道了次品的輕重。

如果還剩下兩種情況，我們只需要讓它和好球比一比，就能找到最終答案了。例如：只剩下1號球重和4號球輕兩種情況，我們只要拿一個(gè)好球和1號球比較就可以了。

綜上所述：N=6時(shí)，我們只需要3次測量，就能保證找到次品，并且知道輕重。

四、N個(gè)球，不知次品輕重

現(xiàn)在我們開始討論最一般的情況：如果N個(gè)球中有一個(gè)次品，不知道次品的輕重，那么最初的可能性有2N種。

理想情況下，如果每次測量都能將可能性壓縮為1/3, 經(jīng)過k次測量，找到次品球并區(qū)分輕重，那么需要滿足：

反過來，測量k次最多能從N個(gè)球中選出那個(gè)不知輕重的次品并區(qū)分輕重，N需要滿足：

然而，這只是N的上限，受到N為整數(shù)的限制，這個(gè)上限不一定能取到。

我們再來詳細(xì)討論一下：

假如一共有N個(gè)球，其中有一個(gè)次品不知輕重，我們測量k次保證能找出這個(gè)次品，那么

第一次測量：將N個(gè)球分為N=a+a+b，天平兩邊各放上a個(gè)球比較

2.1 如果天平平衡

壞球一定位于天平下方的b個(gè)球里，情況有2b種。因?yàn)樵贉y量k-1次，必須保證找到壞球，所以有：

反過來，b需要滿足條件

大家注意，右邊3^(k-1)是一個(gè)奇數(shù)，除以2并不能得到整數(shù)，但是b必須是整數(shù)。所以，這個(gè)條件可以進(jìn)行放縮：

這樣右邊是個(gè)整數(shù)。上面兩個(gè)表達(dá)式其實(shí)沒有區(qū)別。

2.2 如果天平不平衡

如果天平左邊重，說明左側(cè)的a個(gè)球中有一個(gè)比較重的次品，或者右側(cè)的a個(gè)球中有一個(gè)比較輕的次品，情況有2a種。再經(jīng)過k-1次測量，必須找到壞球，所以與剛剛的推導(dǎo)類似，我們依然有：

現(xiàn)在我們已經(jīng)知道了a和b滿足的條件，因?yàn)镹=2a+b，所以這就是測量k次最多能從多少個(gè)球中找到那個(gè)不知道輕重的次品了。

你可以從表中快速找到這個(gè)問題的答案：

從表中很容易找到：如果有12個(gè)球，那么3次測量就能找到次品，并且區(qū)分出次品的輕重了。

五、課后討論

對于這個(gè)問題，其實(shí)還有許多值得討論的地方。

例如：我們在討論出N個(gè)不知輕重的球找次品的公式時(shí)，進(jìn)行了一步放縮。為什么只進(jìn)行一次放縮，而不是測量幾次就進(jìn)行幾次放縮呢？

其次，我們現(xiàn)在的問題是：尋找到次品，并且區(qū)分次品的輕重。如果我們只想找到這個(gè)次品，而不關(guān)心它是輕是重，結(jié)論又應(yīng)該是怎樣？

還有一個(gè)更直接的問題：12個(gè)不知道輕重的小球，測量3次就保證找到次品，并且區(qū)分輕重，這個(gè)結(jié)論我們已經(jīng)得到了?？墒?，具體通過什么步驟，才能找到這個(gè)次品呢？這個(gè)問題依然需要耗費(fèi)一點(diǎn)腦細(xì)胞。

對于這幾個(gè)問題，有想法的同學(xué)，歡迎在評論區(qū)里留言討論。