提要：本文用信息論推導(dǎo)出稱球問(wèn)題的解，并構(gòu)造了的遞推操作的稱量辦法，徹底解決了任意個(gè)球的稱球問(wèn)題。 

關(guān)鍵詞：稱量 信息量 概率 遞推 

經(jīng)典的稱球題目是這樣的：“十二個(gè)外表相同的球中有一個(gè)壞球，它的重量和其它十一個(gè)好球不同，現(xiàn)在有一臺(tái)沒(méi)有砝碼的天平，問(wèn)需要稱幾次就能確保找出那個(gè)壞球”。 

（一）十二個(gè)球稱幾次

做過(guò)這道題目的人知道，答案是3次。不是太難，我們用圖論中的策略樹將稱法記錄如下：

稱3次，從12個(gè)球里找到壞球，并知道壞球的輕重：

這個(gè)結(jié)果是反復(fù)嘗試得到的，雖然直覺上三次應(yīng)該是最低了，但我們終究不能百分之百的確定，我們還是會(huì)問(wèn)，兩次能搞定嗎？或者我們想，十三個(gè)球里面找一個(gè)壞球，三次可以嗎？十四個(gè)呢？……，或者問(wèn)，十個(gè)球里面找一個(gè)壞球要幾次呢？二十個(gè)、四十個(gè)呢？N個(gè)呢？……還有，稱三次最多可以從幾個(gè)球里找到唯一的那個(gè)壞球？四次呢？五次、六次呢？M次呢？解這樣的題目有規(guī)律可循嗎？

一般的，我們要解決以下問(wèn)題：給定任一自然數(shù)N，

⑵給出最小次數(shù)稱球的具體方法。

香農(nóng)在他創(chuàng)立的信息論中，將信息定義為對(duì)“事物不確定性的消除”，消除了多少不確定性，用信息量來(lái)衡量。一個(gè)事件集合中究竟發(fā)生哪一件事情就是不確定的，每個(gè)事件的發(fā)生都有一定的概率，比如明天天氣可以由“晴、多云、陰、雨”幾個(gè)事件組合而成，最終哪種天氣會(huì)出現(xiàn)，今天是不確定的，今天只是知道明天各種天氣的發(fā)生概率，并且知道所有各種天氣出現(xiàn)的概率總和為1。我們來(lái)看看事件集合中發(fā)生某事件的信息大小和該事件發(fā)生的概率之間的關(guān)系。某事件發(fā)生的概率越小，該事件發(fā)生后給我們的“震撼”越大。比如“明天發(fā)生、不發(fā)生地震”這一事件集合中，明天不發(fā)生地震的概率遠(yuǎn)大于發(fā)生地震的概率，所以真的明天發(fā)生了地震，那我們所獲得的信息量就比沒(méi)有發(fā)生地震要大的多。此外，信息具有可加性，“今天地震了又下雨”給我們的信息應(yīng)該是今天發(fā)生了地震和今天下雨兩個(gè)事件的信息的和，而兩個(gè)事件同時(shí)發(fā)生的概率又是這兩個(gè)事件各自發(fā)生概率的乘積，基于此，香農(nóng)將某一“發(fā)生概率為P”的事件的出現(xiàn)帶來(lái)的信息量定義為1/P的對(duì)數(shù)，即1/P?；鶖?shù)r的不同，使得信息量可以有不同的單位，基數(shù)r=2，單位就是比特。比如拋一枚硬幣結(jié)果是“國(guó)徽向上”的信息量是=1比特。

好，我們僅用這一點(diǎn)信息理論，就可以解決上面提出來(lái)的那個(gè)稱球問(wèn)題了。我們的想法是，如果確定12個(gè)球當(dāng)中的壞球需要的信息量是A，而從每次天平的稱量結(jié)果可以至少獲得的信息量是B，那不小于A/B的整數(shù)就應(yīng)該是所需的最小的稱量次數(shù)了。在稱以前，十二只球的任何一個(gè)都可能是壞球，而且概率一樣，都是1/12，所以稱量最終確定了是哪一只后，我們得到了表征“壞球是12個(gè)球中的哪一個(gè)”的=比特信息。另外，表明“好”球、“壞”球是以球的輕重為標(biāo)準(zhǔn)的，所以，如我們從前面策略樹上看到的，最終的結(jié)果不僅是我們找到了壞球，而且知道了壞球比好球是輕了，還是重了，即不管我們是否需要，我們還獲得了表征壞球是“輕”是“重”的=1比特信息。這樣，根據(jù)信息的可加性，最終找到那只壞球以后，我們共計(jì)得到1+= 比特的信息量。

我們?cè)賮?lái)看一次稱量所能給出的信息量。由于是無(wú)法碼天平，稱量能給我們的信息僅僅是天平的右重、左重、平衡三種狀態(tài)。如果我們?cè)O(shè)計(jì)的稱法能夠讓三種結(jié)果等概率出現(xiàn)，都為1/3，則我們就能夠保證一次稱量不管出現(xiàn)什么結(jié)果，我們都可以獲得比特的信息量。如果三個(gè)結(jié)果的概率不相等，由于三個(gè)結(jié)果的概率和為1，無(wú)疑，天平出現(xiàn)“發(fā)生概率”高的那種結(jié)果的話，我們就得不到比特的信息量。這樣，對(duì)12個(gè)球，只要我們的稱量辦法能夠讓三種結(jié)果等概率出現(xiàn)，并且，稱量次數(shù)M能夠使得M≥，即M≥/=2.89，也就是3次，理論上，我們就能稱出壞球。

所以，3次就可以從找到12球里面的找到1個(gè)壞球，并且，因?yàn)?1+)/=/=2.97<>，我們可以試著從13個(gè)球里面找一個(gè)壞球，看一看3次能不能稱出來(lái)；而(1+)/=/=3.03>3，我們可以肯定3次是不可能確保從14個(gè)球當(dāng)中找到一個(gè)壞球并知道其輕重的。如果是N個(gè)球，需要這樣稱M次，而我們所設(shè)計(jì)的稱量辦法可以讓每次天平稱量的三種結(jié)果等概率出現(xiàn)，那只要M≥1+，即M≥=,就一定能找到壞球。我們用{a}表示大于等于a的最小整數(shù)，則有M={=}。如果M恰好等于，則N=。由于N必須為整數(shù)，故N最大只能為。

所以，理論上，我們可以算出，用無(wú)砝碼天平稱2次、3次、4次、5次……，M次，最多可以從4個(gè)球、13個(gè)球、40個(gè)球， 121個(gè)球……，個(gè)球當(dāng)中，找出一個(gè)不知是輕了還是重了的壞球。（結(jié)論1）

（二）尋求稱量方法的預(yù)備問(wèn)題

我們注意到，這個(gè)結(jié)果不是構(gòu)造性的，也就是說(shuō)，上面的結(jié)果只是給出了保證稱出壞球的最低次數(shù)，但是它沒(méi)有告訴我們?nèi)绾稳シQ。我們要知道的不僅僅是“需要稱三次”，還要知道“如何稱這三次”。總球數(shù)多了以后，反復(fù)嘗試的辦法就失效了。

從上面的分析可以看出，天平只有每種狀態(tài)（右重、左重、平衡）出現(xiàn)的概率都為1/3的情況下，一次稱量所給出的信息才能保證最低也是比特，而如果稱量的三種結(jié)果的概率不一樣，出現(xiàn)“發(fā)生概率高”的那種天平稱量結(jié)果的話，我們獲得的信息量一定達(dá)不到，如何去稱的問(wèn)題實(shí)際上是如何實(shí)現(xiàn)天平稱量的三個(gè)結(jié)果等概率（或者盡可能相近的概率）出現(xiàn)，這樣即便天平給出的是最不利的結(jié)果（出現(xiàn)概率最大的稱量結(jié)果），這次稱量還能獲得的足夠多的信息量。保證天平三種狀態(tài)相近概率出現(xiàn)，實(shí)際上就是全部的球如何分組稱量的問(wèn)題，即就是多少球放在天平的左盤，多少球放在右盤，多少球放在下面待稱?，F(xiàn)在，我們?nèi)匀粡男畔⒘咳胧謥?lái)分析，作為準(zhǔn)備，我們需要從一個(gè)更為簡(jiǎn)單的問(wèn)題開始。

已知12個(gè)球中有一個(gè)壞球比正常的球重（或輕，分析的過(guò)程一樣），用無(wú)法碼天平要幾次可以稱出來(lái)。與前面的題目不一樣的是我們已經(jīng)得到了表征壞球輕重的=1比特信息。這時(shí)，找到壞球就只需要的信息，當(dāng)然，我們還是要/=2.26次，也就是3次，但是/=3，我們應(yīng)該可以用3次稱量從27只球當(dāng)中找出一個(gè)已知較輕還是較重的壞球了。我們的想法是對(duì)的。稱法很簡(jiǎn)單，假設(shè)壞球較重，將27個(gè)球編號(hào)1-27，取1-9,10-18號(hào)球，分別放天平的兩側(cè)，哪側(cè)重則壞球便在哪側(cè)的9個(gè)球中，比如天平平衡，則壞球在19-27號(hào)的9個(gè)球中。不管第一次稱量結(jié)果怎樣，再將包含壞球的那9個(gè)球等分成3個(gè)的三組，繼續(xù)上面的稱法，就得到包含壞球的一組3個(gè)球，取其中的兩個(gè)再稱一次，結(jié)果就出來(lái)了。可以看出由于每次都可以將包含壞球的那一組球等分成三部分，我們每次稱量天平出現(xiàn)右重、左重、平衡三種狀態(tài)的概率一樣，那么每次天平稱量結(jié)果給出的信息都是比特，所以三次就正好獲得所需的比特信息。

為了下面分析的需要，我們將題目變化得稍微復(fù)雜一些，并且將球的總數(shù)設(shè)為N：我們需要從N個(gè)球中找到一個(gè)壞球，我們不知道那個(gè)壞球是輕還是重了，但我們知道，如果壞球出現(xiàn)在N個(gè)球的前面X個(gè)球中，那一定是重了，如果出現(xiàn)在剩下的(N-X)個(gè)球中，那一定是輕了（把題目改成這樣，純粹是后面分析的需要），即我們只要知道了壞球是哪個(gè)，那壞球是輕是重就知道了，所以，找到壞球所需的信息量還是比特，用{ /}次稱量一定可以稱出來(lái)。

下面開始，敘述更加繁瑣，如果大家對(duì)推導(dǎo)、證明過(guò)程沒(méi)有興趣，可以只閱讀每節(jié)最后歸納的結(jié)論。

為了敘述的方便，我們將表述“壞球出現(xiàn)在N個(gè)球的前面X個(gè)球中，那一定是重了，如果出現(xiàn)在剩下的(N-X)個(gè)球中，那一定是輕了”想象成一次稱量（X；N-X）的結(jié)果（我們?cè)谇驍?shù)少的一側(cè)加上標(biāo)準(zhǔn)重量的球），我們稱這次想象的稱量為第一次稱量，即我們的第一次稱量得到了壞球是輕是重的“分布”，這樣，我們要研究的就是后續(xù)的第二次、第三次……的稱量操作方法。

第二次稱量的稱法是這樣的：我們盡可能將X個(gè)球均分成3組，這樣各組之間的球數(shù)差不會(huì)超過(guò)1個(gè)。如果這3組中包含了壞球，那壞球一定是重了，故我們記為重組1、重組2、重組3。同樣，余下的N-X個(gè)球，也這樣分成3組，分別記為輕組1、輕組2、輕組3，如果這3組中包含了壞球，那壞球一定是輕了。我們分別取重組、輕組各1組，合成新的三部分，由于原來(lái)輕重各自組的球數(shù)差不會(huì)超過(guò)1個(gè)，這樣適當(dāng)?shù)娜〗M安排可以使得三部分的球數(shù)差也不會(huì)超過(guò)1。我們的目的是將要進(jìn)行稱量的球最為均勻地分成三部分（如果N是3 的正整數(shù)冪，那三部分的球數(shù)都相等）。比如，如果：重組1球數(shù)≥重組2球數(shù)≥重組3球數(shù)，輕組1球數(shù)≥輕組2球數(shù)≥輕組3球數(shù)，我們組合的三部分就可以是（重組1、輕組3）、（重組2、輕組2）、（重組3、輕組1）。我們對(duì)這三部分的球進(jìn)行三種操作：1、“留”（指這部分球留在前一次“想象”稱量時(shí)所在天平的盤中）。2、 “換”（指這部分球前一次“想象”稱量在左盤的，現(xiàn)在要換到右盤；原來(lái)在右盤的，現(xiàn)在要換到左盤。3、“下”（指不管前一次“想象”稱量在天平的哪一側(cè)盤中，現(xiàn)在這部分球要拿到天平的下面）。我們可以分別稱他們“留部分”、“換部分”、“下部分”。因?yàn)槿糠智驍?shù)差最多為1，這樣我們完成上述留、換、下操作以后，左右盤的球數(shù)最多也只相差1個(gè)，所以，最多加上1個(gè)標(biāo)準(zhǔn)球，我們就可以進(jìn)行這次稱量。

進(jìn)行這樣操作的目的，仍然是為了這一次稱量三個(gè)結(jié)果的出現(xiàn)能盡可能地等概率，它是前一次稱量結(jié)果下的條件概率，不論這次天平稱量是什么結(jié)果，我們都可以排除掉三部分中的兩部分存在壞球的可能。如果這一次稱量，天平的傾斜方向與第一次稱量結(jié)果相同，那壞球一定在“留部分”當(dāng)中；如果這一次稱量，天平的傾斜方向與第一次稱量結(jié)果相反，那壞球一定在“換部分”當(dāng)中；如果天平平衡，那壞球一定在天平“下部分”球當(dāng)中，三部分的球數(shù)對(duì)應(yīng)著天平三種稱量結(jié)果的概率。不管那一種結(jié)果，含有壞球的球的總數(shù)最多就只剩{N/3}個(gè)了，而且我們?nèi)匀恢?，如果壞球出現(xiàn)在{N/3}個(gè)的哪些球中，那一定是重了；如果出現(xiàn)其他的球中，那一定是輕了。

接著我們對(duì)這{N/3}如法炮制，分成6各組，再組合成3部分，稱量之后，含有壞球的總數(shù)就剩{{N/3}/3}個(gè)了……,如此下去，只要{}={/}次稱量（如果N是3 的正整數(shù)冪，那就正好是/次），就可以從N個(gè)球當(dāng)中找到壞球了，或者說(shuō)，M次稱量最多可以從個(gè)球當(dāng)中找到一個(gè)已知壞球輕重“分布”的壞球。

歸納一下：

如果我們知道，壞球出現(xiàn)在N個(gè)球的前面X個(gè)球當(dāng)中，那它一定是重了；如果出現(xiàn)在余下的N-X個(gè)球里面，那一定是輕了，用沒(méi)有砝碼的天平，稱1、2、3、4……M次，能夠確保從3、9、27、81……個(gè)球中找到壞球。我們有稱量的可操作的方法。（結(jié)論2）

（三）十二個(gè)球的稱法

首先，12可以被3整除，無(wú)疑第一次稱量要將12個(gè)球分成了4、4、4三組，天平的左盤、右盤、下面各放一組。

一、天平傾斜（由于右重、左重兩種情況是對(duì)稱的，我們只分析左重的情況），壞球在天平上的8個(gè)球里面，而且知道如果壞球在左邊4個(gè)球的話一定是重了，在右邊的4個(gè)球里的話一定是輕了，它是前面第二節(jié)分析過(guò)的情況，我們用結(jié)論2，再兩次就可以稱出壞球是8個(gè)球里面的哪一個(gè)了。

二、天平平衡，則壞球一定在天平下面的4個(gè)球里。第二次稱量我們有三種稱法：（1左、1右、2下）；（2左、1+S右、1下）；（1+S左、2右、1下）（+S表示從第一次稱量已經(jīng)知道的8個(gè)好球里面拿一個(gè)加到天平上,參與稱量。同樣，后面的兩種稱法是對(duì)稱的，下面作為一種分析）。算一下每一種稱法各個(gè)結(jié)果的信息量。第二次稱量第一種稱法（1左、1右、2下）：如果天平平衡，壞球在下面的2個(gè)球里，我們獲得的信息量：（1+）-（1+）=1比特，即還剩余1+=2比特信息留到第三次稱量；如果天平右重（或左重），壞球一定在天平上的兩個(gè)球里，而且有了壞球的輕重的信息，則獲得信息量是（1+）-=2比特，剩余=1比特信息。第二次稱量第二種稱法（2左、1+S右、1下）：如果天平平衡，我們知道壞球就是下面的那個(gè)球，獲得了（1+）-（1+）=2比特信息；如果天平傾斜，壞球在天平上的三個(gè)球里，而且有了壞球的輕重的信息，我們獲得（1+）-=比特信息。我們現(xiàn)在要考慮的是兩種分組稱法各自最不利情況下的信息量，即要比較的是兩種稱法下各自獲得的最低信息量。無(wú)疑，第二種稱法是可行的，天平稱量的三種可能結(jié)果中的最低信息量有 比特，比前一種分組下三種稱量結(jié)果的最低信息量1比特要大，所以應(yīng)該選擇第二種稱法（2左、1+S右、1下）。順便說(shuō)一下，第一種稱法（1左、1右、2下）兩種結(jié)果下，最多剩余的信息量還有2比特（原因就在于這次稱量三種結(jié)果的概率太不均勻，剩余的信息量太大），是不能用剩下的第三次，也就是最后一次稱量得到結(jié)果的，所以，第二次稱量只有第二種稱法才是可行的。

最后，剩下的第三次稱量很簡(jiǎn)單，如果是第二種稱法的第一種結(jié)果，天平平衡，從其他的11個(gè)球當(dāng)中取一個(gè)（好球），稱一下剩下的這只壞球，壞球的輕重就知道了。如果是第二種結(jié)果，一次稱量三個(gè)已知壞球輕重“分布”的方法，還是用結(jié)論2，也不用說(shuō)了。（參見前面給出的策略樹）

從上面的稱量辦法可以看出，天平的第一次傾斜就給出了壞球輕重的1比特信息。我們從信息的可加性很容易理解這一點(diǎn)。我們將壞球是哪一個(gè)和壞球是輕是重兩種信息分開看，假設(shè)第一次稱量時(shí)我們已經(jīng)得到了哪一個(gè)是壞球的信息，知道了壞球是天平上的哪一個(gè)球，那第一次稱量天平的左斜還是右斜不就告訴了我們壞球是輕是重了嗎？其實(shí)，我們得到的結(jié)論2也說(shuō)明了這一點(diǎn)。

歸納一下：我們有了12個(gè)球找到壞球的稱量操作辦法，即盡可能將要稱量的球按球數(shù)均勻分組，每次稱量，以三種稱量結(jié)果給出的最低信息量，對(duì)球各種分組方法的稱量進(jìn)行比較，取最大者所指示的辦法，完成這次稱量。

（四）十三個(gè)球的稱法

按照“每次稱量要獲得最不利結(jié)果情況下的最大信息量”的原則對(duì)球進(jìn)行分組，我們終于有了稱球問(wèn)題的可操作的解決辦法?，F(xiàn)在把這一結(jié)論推廣到13個(gè)球。

第一節(jié)分析過(guò)了，從信息量的角度看，稱量三次，最多可以從13個(gè)球當(dāng)中找到一個(gè)不知是輕了還是重了的球。我們將要稱量的13個(gè)球盡可能均勻地分成三組，最為均勻只能是4、4、5。由于天平兩邊的球數(shù)相等，稱量才有意義，我們將球數(shù)為4的兩組分別放到天平的兩端進(jìn)行第一次稱量，但是我們馬上就看到，如果此時(shí)天平平衡，壞球一定在剩下的5個(gè)球當(dāng)中，而根據(jù)結(jié)論1，用剩下的2次是無(wú)法稱出壞球的。我們?cè)賹?duì)上面的稱法作一下信息量的分析，由于第一次稱量我們只獲得（1+）-（1+）=，達(dá)不到一次稱量所能獲得的最大信息量，而剩余的信息量1+ >2，所以剩下的兩次就不可能再稱出壞球并知其輕重了。（其他的分組方法更為不均勻，比如5、5、3分組，如果天平傾斜，相當(dāng)于我們要從已知壞球輕重的10球中找到壞球，根據(jù)結(jié)論2是不可能的）

現(xiàn)在我們退一步。由于剩余的信息量1+超過(guò)了兩次稱量所能獲得的最大信息量，我們想是不是能夠不要知道壞球的輕重，而僅僅把壞球找出來(lái)，這樣我們所需的信息量應(yīng)該只有，低于兩次稱量所能得到的信息量2了。果然可行，稱量方法如下，其中S表示已經(jīng)在第一次稱量中已經(jīng)知道是好的球：

稱兩次，從5個(gè)球里找到壞球，不需要知道壞球的輕重：

*說(shuō)明：天平兩次都是平衡的情況下，我們就無(wú)法得到壞球是輕是重的1比特信息，前面12球的策略樹上，我們加上了這種情況。

就是說(shuō)，不需要知道壞球是輕了還是重了的話，稱量3次我們也能確保找到壞球，只是不能確保知道壞球的輕重。

注意這里的結(jié)果（不要知道壞球輕了還是重了的稱量結(jié)果）和已經(jīng)知道壞球的是輕是重的稱量結(jié)果的不同。對(duì)于相同的總球數(shù)N，雖然最終獲得的有用信息是一樣的，都是（兩種情況下都不再需要壞球是輕是重那1比特信息了），但是，是否事先知道“壞球是輕是重”這一信息，對(duì)稱量能獲得的有用信息影響很大。我們用N=9個(gè)球進(jìn)行的第一次稱量做個(gè)說(shuō)明。無(wú)論我們是否知道“壞球是輕是重”這一信息，按照前面的分析，我們的分組都應(yīng)該是（3左，3右，3下）。如果我們知道“壞球是輕是重”這一信息，那按照結(jié)論2，天平的任何稱量結(jié)果都給出了比特信息，再有一次稱量我們就可以找到壞球了；而如果我們不知道“壞球是輕是重”這一信息，天平平衡我們得到比特信息，天平傾斜我們獲得了1+-=1+比特信息，但是由于不再需要壞球是輕是重那1比特信息了，此時(shí)，最終的有用信息只有，剩余的信息有，再有一次稱量是不能找到壞球的。所以，總球數(shù)一樣，“不要知道壞球輕了還是重了”的稱量次數(shù)和“已經(jīng)知道壞球的是輕是重而不需要知道壞球輕重”的稱量次數(shù)不一樣，雖然最終獲得的有用信息是一樣的?！皦那蜉p重”的信息在稱量的過(guò)程中起了作用。

違背了結(jié)論1,十三個(gè)球不能三次稱出壞球或者找到了壞球卻不確保知其是輕了還是重了的原因，是第一次稱量沒(méi)有獲得足夠大的信息（13球無(wú)法平均分成三組），因?yàn)樘炱缴系那虮仨毷桥紨?shù)，這樣我們只能在天平上放8個(gè)球。按照結(jié)論2，余下的兩次稱量最多可以從9個(gè)球當(dāng)中找到知道輕重的壞球，所以，如果我們事先手上有一只已知的好球，可以叫它標(biāo)準(zhǔn)球（它與好球有相同的質(zhì)量，但我們一眼可以將它和其它13個(gè)球區(qū)分開來(lái)，比如它有不同的顏色），我們就可以在天平上放9個(gè)球，加上這只標(biāo)準(zhǔn)球，我們的第一次稱量的球的分組變成（5右、4+S左、4下），此時(shí)，如果天平傾斜，我們獲得（1+）-=比特信息；如果天平平衡，我們獲得（1+）-（1+）==比特信息，通過(guò)添加一只標(biāo)準(zhǔn)球，我們的第一次稱量獲得了更為均衡的信息量，三種結(jié)果都比前面（4左、4右、5）出現(xiàn)天平平衡情況的信息量要多。所以標(biāo)準(zhǔn)球的加入，“改善”了稱量的手段，使稱量結(jié)果給出的信息量更為均勻。

這樣，有了標(biāo)準(zhǔn)球，將13個(gè)球按照（5右、4+S左、4下）分組，天平平衡，仿照12個(gè)球的方法，我們可以從邊上的4個(gè)球里稱兩次找到壞球（參見本文開始給出的策略樹）；天平傾斜，按結(jié)論2，我們可以從天平上的9個(gè)球稱兩次找到壞球。不管第一次稱量的結(jié)果如何，余下的兩次稱量，一定可以找到壞球，而且知道壞球輕重，這樣我們就徹底解決了13個(gè)球的問(wèn)題。

我們注意到，額外的標(biāo)準(zhǔn)球只需要在第一次稱量時(shí)使用，第一次稱量完成后，我們就可以知道原來(lái)的13個(gè)球當(dāng)中哪些是好球，而可以將他們作為標(biāo)準(zhǔn)球了。

歸納一下：要么找到的壞球不確保能知道它的輕重，要么我們事先有一只標(biāo)準(zhǔn)重量的球，只要具備這兩個(gè)條件之一，我們就可以通過(guò)3次稱量，找到13個(gè)球中的壞球。 

（五）N個(gè)球的遞推稱法

從13個(gè)球的稱量辦法，我們可以看到，有了標(biāo)準(zhǔn)球，“13個(gè)球里稱3次找到一個(gè)不知輕重的壞球”可以分解成“4個(gè)球里稱2次找到一個(gè)不知輕重的壞球”和“9個(gè)球里稱2次找到一個(gè)已知輕重‘分布’的壞球”。13個(gè)球的第一次稱量（5右、4+S左、4下）可以寫成（9；4）。同樣，“13（9+4）個(gè)球里稱3次找到一個(gè)不知輕重的壞球”加上結(jié)論2當(dāng)中的“27球里稱3次找到一個(gè)已知輕重（分布）的壞球”又可以作為“40（27+13）個(gè)球稱4次找到一個(gè)不知輕重的壞球”問(wèn)題的第一次稱量。我們可以將40個(gè)球按照（14右、13+S左、13下）或（27；13）分組，天平平衡，按上節(jié)的稱法，我們可以從邊上的13個(gè)球里稱3次找到未知輕重的壞球；天平傾斜，我們可以從天平上的27個(gè)球稱3次找到已知輕重（分布）的壞球，我們就解決了40（27+13）個(gè)球找到壞球的問(wèn)題。

其實(shí)，有了標(biāo)準(zhǔn)球，“4個(gè)球里稱2次找到一個(gè)不知輕重的球”一樣也可以向前遞歸成分解成“1個(gè)球里稱1次找到一個(gè)不知輕重的球” （實(shí)際上就是用標(biāo)準(zhǔn)球稱一下這個(gè)球的輕重）和“3個(gè)球里稱1次找到一個(gè)已知輕重（分布）的壞球”。（而如果沒(méi)有標(biāo)準(zhǔn)球，如同3次從13個(gè)球里不能確保稱出壞球輕重一樣，兩次我們不能確保稱出4個(gè)球里的壞球輕重的）。

按照這樣遞推的辦法，從N個(gè)球當(dāng)中找到一個(gè)壞球，我們就有了下面的結(jié)論：有1個(gè)標(biāo)準(zhǔn)球，用無(wú)砝碼天平，稱量M次，我們最多可以從（-1）/2個(gè)球里面找到一個(gè)壞球，并且，知道它是比好球（標(biāo)準(zhǔn)球）輕了還是重了。我們的稱量辦法是：

將[（-1）/2-1]/3=(-1)/2個(gè)球放在天平下面，而將剩下的個(gè)球加上一個(gè)標(biāo)準(zhǔn)球，分放到天平的兩側(cè)盤里。我們稱之為稱量[;(-1)/2]。天平傾斜，問(wèn)題歸結(jié)為天平上面的個(gè)球稱M-1次找到已知輕重（分布）的壞球的問(wèn)題，我們用結(jié)論2可以解決；天平平衡，問(wèn)題歸結(jié)為天平下面的(-1)/2個(gè)球稱M-1次找到未知輕重的壞球的問(wèn)題……，如此逐次遞推下去，稱球問(wèn)題得到解決。

我們將結(jié)果匯總于下表。表中同時(shí)收進(jìn)了“已知壞球輕重”、“有無(wú)標(biāo)準(zhǔn)球”、“是否需要知道壞球輕重”幾種組合情況。 

表一：用無(wú)砝碼天平稱量M次最多可以從多少個(gè)球中稱出壞球

我們從數(shù)學(xué)表達(dá)式可以很清楚地看出遞歸性。由于=+ ++…… +1= +，分組就是按照[;]進(jìn)行,將個(gè)球加上一個(gè)標(biāo)準(zhǔn)球放在天平的兩邊，將個(gè)球留在天平下面，而= ++…… +1=+，這樣的遞歸可以一直做到最后分組稱量（1；3）。

如果總球數(shù)N在M次和M-1次稱量所能找出壞球的最多球數(shù)之間，即<>,則我們一樣留下在天平下面，剩下的如果是偶數(shù)，則天平的兩邊各取一半；如果是奇數(shù)則加上標(biāo)準(zhǔn)球后天平的兩邊各放一半，同樣可以完成第一次稱量，并遞推下去。所以，上述的標(biāo)準(zhǔn)的稱量辦法就可以完成任意個(gè)球的稱量，我們完整地?fù)碛辛苏页觥癗個(gè)球當(dāng)中的一個(gè)未知輕重的壞球”的嚴(yán)格的稱量方法。我們將表一轉(zhuǎn)換一下，得到表二；

表二：用無(wú)砝碼天平確保找出N個(gè)球中的唯一一個(gè)重量不一樣的壞球需要稱量的次數(shù)

正如我們前面分析過(guò)的，同樣的球數(shù)里面找到壞球，稱量次數(shù)由于“有無(wú)標(biāo)準(zhǔn)球”和“是否需要知道壞球的輕重”的不同，可能是不一樣的，原因就在于前者可以均衡稱量各個(gè)結(jié)果的信息量，使最不利稱量結(jié)果出現(xiàn)時(shí)的信息量達(dá)到最大；后者表明了我們需要獲得的總信息量大小的不同。

順便說(shuō)一下，1個(gè)球里面找一個(gè)壞球，題目的意義僅僅是，如果我們有標(biāo)準(zhǔn)球，稱一下這個(gè)球是輕了還是重了；2個(gè)球里面有一個(gè)壞球，也只有提供了標(biāo)準(zhǔn)重量的球才有意義。

1) N＜(-1)/2， M次稱量就足夠了； N=(-1)/2，M次稱量能夠確保找到壞球，但不能確保知道壞球比標(biāo)準(zhǔn)球輕還是重；如果另有一個(gè)標(biāo)準(zhǔn)球，那么稱M次能夠確保找到壞球，并知道壞球比標(biāo)準(zhǔn)球輕還是重；N=(-1)/2+1，只有在另有一個(gè)標(biāo)準(zhǔn)球同時(shí)不需要知道壞球比標(biāo)準(zhǔn)球輕還是重的情況下，才能確保找到壞球。具體如表一、表二所示

2) (-1)/2=(-1)/2 +，我們按照[(-1)/2; ]對(duì)待稱的球進(jìn)行分組，進(jìn)行稱量，天平傾斜，則應(yīng)用結(jié)論2，完成稱量；如果天平平衡，則再次將天平下面的(-1)/2 個(gè)球按[；]分組，進(jìn)行稱量。如此遞推稱量下去，便是解決稱球問(wèn)題的可操作的稱量方法。 

（六）補(bǔ)充證明

前面對(duì)（12球、13球等）不同分組辦法的稱量結(jié)果的信息量進(jìn)行了測(cè)算，其過(guò)程可以看成是用信息論對(duì)這些特例的稱量辦法作出的推導(dǎo)或證明。為嚴(yán)格起見，現(xiàn)在我們將證明推向一般，給出N個(gè)球的分組辦法的證明。因?yàn)?img doc360img-src='http://image102.360doc.com/DownloadImg/2017/01/1009/88948161_56' src="http://pubimage.360doc.com/wz/default.gif"/>（M為稱量次數(shù)）可以被3整除，為了下面表述的方便，我們以“沒(méi)有標(biāo)準(zhǔn)球，同時(shí)需要知道壞球輕了還是重了”為例。其他三種球數(shù)的情況大同小異，只是由于總球數(shù)不能被3整除，表述起來(lái)困難一些。

如我們?cè)谏弦还?jié)看到的，由于右重和左重是對(duì)稱的，稱量可以看成是將全部的球分成了兩組，即天平上的一組（分到左右盤）和天平下的一組，我們?cè)儆眯畔⒄搶?duì)分組球數(shù)進(jìn)行推導(dǎo)。

設(shè)我們從N個(gè)球中留K個(gè)球在天平的下面，這樣就有N-K個(gè)球分放到天平的兩邊盤中，如果

1、   天平傾斜（比如右重）我們獲得的信息量為：;

2、    天平平衡我們獲得的信息量為：

為使得兩種結(jié)果所獲得的信息量均衡，必須有：

即：

即我們?nèi)】偳驍?shù)的三分之一留在天平下面，而將其余的三分之二分放到天平上的兩端去稱量。當(dāng)然，這一結(jié)果與前面遞推稱量辦法采用的球的分組方法是一致的。 

（七）推廣

我們用信息論徹底解決了“用沒(méi)有砝碼的天平在N個(gè)球當(dāng)中找唯一一個(gè)重量不一樣的壞球”的問(wèn)題，這結(jié)論還可以作進(jìn)一步的推廣。我們可以猜測(cè)（他們的稱法驗(yàn)證過(guò)于復(fù)雜）：N個(gè)球當(dāng)中有K個(gè)壞球比其它球重了，而且這K個(gè)球重量一樣，我們可以知道需要用無(wú)砝碼天平稱量次，就可以找到全部K個(gè)壞球；如果我們還不知道這K個(gè)球比其它球重了或者輕了，只知道這K個(gè)球重量一樣，我們需要用無(wú)砝碼天平稱量，找到這K個(gè)壞球，并且知道他們是重了還是輕了；如果K個(gè)球有的比好球重，有的比好球輕，只是它們與好球重量的差距一致，那我們用無(wú)砝碼天平稱量，需要次，才能找到全部K個(gè)球，并且知道他們各自是重了還是輕了……等等。上述各個(gè)結(jié)論對(duì)我們的實(shí)際工作，比如產(chǎn)品檢測(cè)，應(yīng)該還有一定的實(shí)際意義。