趣味數學（四）巧用天平

有12個外表一模一樣的球，其中有一個壞球重量不同於其他11個。隻允許使用三次天平，如何找出壞球並弄清是輕是重？

這是一個廣為人知的問題，網上應有不少答案。現在要介紹的，是利用信息論裏的熵來幫忙找出壞球。

信息論裏最重要的概念就是熵。如果一個概率分布為 (P)=(p_1,p_2,...,p_n),則其熵為H(P)=-(p_1log(p_1)+p_2log(p_2)+...+p_nlog(p_n))。它是一個非負值，可用來度量一個概率分布的不確定性，也就是信息量。這句話可以這麽理解：當一個隨機事件的結果未知以前，它具有不確定性，但當結果已知以後，不確定性便轉化為信息量了。

信息論裏一個重要的結論是，一個概率分布如有n個可能的結果，則當n個結果概率等可能時，信息量最大。比方說，下麵兩個分布： (1/3,1/3,1/3)和(3/8,3/8,2/8)，前者的信息量更大。

我們用天平稱球的過程，就是獲取信息的過程，所以要盡可能獲得大的信息量，而這又依賴於我們如何使用天平。一次使用天平的結果，有三種可能，就是左輕右重，左右相等和左重右輕。如果能夠合理使用，使三種結果的概率盡可能相等，所獲的信息量就盡可能大了。

如果三個球中隻有一個壞球且知其輕重，稱一次就可輕易找到壞球；而如果九個球中隻有一個壞球且知其輕重，則稱二次也可輕易找到壞球。類似的，如果二十七個球中隻有一個壞球且知其輕重，則稱三次也可輕易找到壞球。

我們的問題難在不知壞球是輕還是重，否則就輕而易舉了。解法如下：

先用從1到12給球標上號並將它們分為三組：{1,2,3,4},{5,6,7,8}和{9,10,11,12}。壞球在三組中的概率是一樣的，都是1/3。取出兩組分別放在天平的兩端，比如{1,2,3,4}放左端，{5,6,7,8}放右端。這樣獲得的信息量最大，因為左右相等，左輕右重和左重右輕的概率均是1/3。

如果左右相等，壞球就在第三組中。將{1,2,3}放在左邊，{10,11,12}放在右邊稱第二次。如兩邊相等，9號就是壞球，再稱一次就能確定輕重，否則，壞球必在{10,11,12}中且輕重已知，再稱一次也可找到答案。

如左輕右重，這時壞球要麽在{1,2,3,4}中且為輕, 要麽在{5,6,7,8}中且為重。然後考慮下麵的分組：{1,2,9},{5,6,7}和{3,4,8}，並將{1,2,9}和{3,4,8}分別放在天平的左右兩端稱第二次。這樣做是因為壞球在三組中的概率最為接近，分別是2/8，3/8和3/8，而且稱球後三種結果的概率也盡可能相等。如兩邊相等，則壞球必在{5,6,7}中且為重，再稱一次就可找到答案了。現假設兩邊不等。如左輕則壞球必在{1,2}和8中，1和2再稱一次便可得答案。如左重則壞球在3和4號球中，再稱一次也可知結果。

左重右輕的情形可同法處理，就不贅述了。

大家不妨試試看。祝你成功！

請閱讀更多我的博客文章>>>