1000桶水，其中一桶有毒，豬喝毒水後會在15分鐘內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？

2020-06-10知識

這道題看起來像是一道演算法題，本質上卻是披著豬皮的 消息理論 問題。解答這道題並不是我的目的，我的目的是用消息理論的思維來思考，達到觸類旁通，一通百通。

用消息理論去思考的另一個好處就是，消息理論給了這類問題的一個邊界，讓我們在邊界範圍內思考問題。很難想象，70多年前的山農已經用嚴格的理論證明為這類問題設定了一個極限，任何想逾越這個極限去解決問題的人最後都會被證明是徒勞的。

這也是理論武裝頭腦的好處，當別人還在嘗試是否有更優的解法時，你可以直接給出最優答案，用消息理論降維打擊。即使我可能暫時無法想出具體的方案，但我知道這類問題的一個理論極限在哪裏，沒有必要為超越極限做無用功。

所以，在解題之前我覺得有必要補充一下理論知識，讓我們了解一下消息理論中「 資訊熵 」。

資訊熵

1. 熱力學中的熵

熵的概念最早起源於物理學，用於度量一個熱力學系統的無序程度，也就是系統混亂程式。

熵增定律 指出：

在一個孤立系統裏，如果沒有外力做功，其總混亂度（熵）會不斷增大

熵增定律讓我們知道，如果將一杯熱水和一杯涼水倒在一起，並且不對水杯中的水做功，這杯水的冷熱分子最終一定呈最混亂的分布，也就是最終整體溫度均勻分布，絕對不會出現冷熱水分層的現象。

如果把宇宙當成一個孤立系統，那麽宇宙一定是從有序變為無序混亂的狀態，當宇宙的熵達到最大值時，宇宙中的其他有效能量已經全數轉化為熱能，所有物質溫度達到熱平衡。這種狀態稱為熱寂。這樣的宇宙中再也沒有任何可以維持運動或是生命的能量存在。

2. 消息理論中的熵

在消息理論中，熵的概念和熱力學中是類似的，描述的是「 資訊的不確定程度 」。

熱力學熵： 系統的混亂程度

資訊熵： 資訊的不確定性的度量

所以資訊中的不確定性類似於熱力學中系統的混亂程度。

所以也就是說，資訊的不確定程度越大，資訊熵也就越大。那什麽樣的資訊不確定程度大呢？

比如拋一枚硬幣，如果我來猜正反的話，那麽我基本只能靠瞎蒙，因為不確定程度很大，正反的概率都是0.5。對於拋一次硬幣猜正反這類事件來說，它的不確定程度很大，資訊熵也很大。

如果中國男足和巴西男足比賽，讓我來猜勝負，那麽我幾乎可以斷言，巴西隊一定會贏。也就是巴西隊和中國隊勝負這個事件的不確定程度很小，資訊熵也就很小。

如果比賽後巴西隊真的贏了，那麽這條資訊的資訊量幾乎為零，因為這條資訊幾乎沒有降低資訊的不確定度。

上面提到了 資訊熵、資訊、資訊量 ，它們之間的比較如下：

資訊熵 是一個絕對值，用來衡量資訊不確定程度的絕對大小。

凡是在一種情況下能減少不確定性的任何事物都叫 資訊， 否則叫作廢話。比如經常會碰到有人絮絮叨叨，不知所雲，說了好久不知道要表達什麽。從消息理論的角度來看，這些話就不包含資訊。

資訊量 是一個相對值，表示的是在某個具體事件發生以後所帶來的的資訊。顯然，事件發生的概率越低，當事件發生了以後帶來的資訊越大，說明資訊量越大。比如福彩35選7，如果有人直接告訴你這7個數碼，開獎了以後竟然是一樣的，那麽這條資訊的資訊量就超級大。又比如某報刊登了男明星A出軌的訊息，因為我們已經知道男明星A本身就很渣，出軌也在情理之中，所以這則訊息的資訊量就很低。

上面都只是定性的分析，山農把隨機變量 X 的熵值 Η定義如下，其值域為{ x 1, ..., xn }

\mathrm{H} (X)=-\sum _{{i}}{{\mathrm {P}}(x_{i})\log _{b}{\mathrm {P}}(x_{i})}

b是對數所使用的底。當 b = 2，熵的單位是 bit 。

P為 X 的概率質素函數（probability mass function），我們可以理解為事件xi 發生的概率。

公式看起來可怕，其實非常簡單。

讓我們用拋硬幣來舉例，「拋一次硬幣是正面」這個隨機變量X的 資訊熵 為

\mathrm{H} (X)=-(\frac{1}{2}log _{2}\frac{1}{2} + \frac{1}{2}log _{2}\frac{1}{2}) = -log_{2}\frac{1}{2}=1

也就是拋一次硬幣是正面這個事件的資訊熵只需要1 bit，也就是只需要用1位的二進制數就可以表示這個資訊大小。

題目的簡化版本

在我們學習了資訊熵的知識以後，讓我們再來看題目。原題其實略微復雜一些，先將題目簡化一下。

1000桶水，其中一桶有毒，豬喝毒水後會在15分鐘內死去，想用15分鐘內找到這桶毒水，至少需要幾頭豬？

上面這道題其實也是當年google的一道面試題，只不過面試題中的小白鼠在這裏被替換成了豬。原題是多次試驗問題，簡化後的版本是單次試驗，更容易看到這道題的本質。於是我們利用上面介紹的資訊熵的知識來求解一下。

首先，」 1000桶水其中有一桶有毒 「這個隨機變量X的 資訊熵 為

\mathrm{H} (X)=-log _{2}\frac{1}{1000} =9.966

1只豬喝水以後的要麽活著，要麽死去，一共有兩種狀態，所以」1只豬喝完水以後的狀態「這個隨機變量Y的資訊熵為

\mathrm{H} (Z)=-(\frac{1}{2}log _{2}\frac{1}{2} + \frac{1}{2}log _{2}\frac{1}{2}) = -log_{2}\frac{1}{2}=1

n只豬喝完水會有 2^n 種狀態，即"n只豬喝完水以後的狀態"這個隨機變量Y的資訊熵為

\mathrm{H} (Y)=-\sum _{{i=1}}^{2^n}{\frac{1}{2^n}}{\log _{2}{\frac{1}{2^n}}}=-\log _{2}{\frac{1}{2^n}}=n

所以，按照題目要求，如果至少需要n頭豬能夠找到這桶毒水，那麽隨機變量Y的資訊熵必須要大於隨機變量X的資訊熵，也就是

H(Y) >= H(X) ，也就是 n >= 9.966，即 n = 10

當我們用資訊熵算出來了n的最小值以後，我們就可以堅信，理論上n=10一定是最優解，任何想方設法想找到小於10的值都是徒勞的。

其實，上面的資訊熵計算的簡化版本可以寫成如下更好理解的形式

2^n \ge 1000

同樣可以解得 n = 10 ，雖然形式簡單，但我們一定要記住它背後的原理是資訊熵。

至於到底采用什麽方案，這涉及到術的層面，即使我們暫時想不到，我們也會有努力的方向，並且知道努力的邊界在哪裏，不會做類似尋找永動機的事情。

下面我們來看下圖具體的方案

我們將1000桶水按照2進制編碼，如上圖第一行，需要10位二進制數。於是有

第1桶水對應上圖最右側位置1的數碼是1，其它數碼都是0，也就是00000 00001b，其中b代表二進制數。

第10桶水對應上圖位置4和位置2的數碼是1，其它數碼都是0，也就是 00000 01010b。

同理，任意一桶水，都可以對應上面唯一的一個二進制數。

於是，我按照如下方案讓豬進行喝水，如上圖所示：

1號豬喝位置1的數碼是1的水，也就是1、3、5、7、9 ...

2號豬喝位置2的數碼是1的水，也就是2、3、6、7、10 ...

...

6號豬喝位置6的數碼是1的水，也就是32、33、34、35、36 ...

...

如果15分鐘後1，3，5號豬被毒死，那麽對應的二進制編碼就是00000 10101b，也就是21號水桶有毒。更一般的，豬死的任何一種排列方式都對應了二進制的唯一編碼。

這裏為什麽采用二進制的編碼方式？

首先，我們要理解為什麽電腦內部運算都采用二進制的方式，這是因為開關電路在電腦中實作起來非常簡單，而開關兩種狀態正好對應了二進制的0和1。老式的電腦都是用繼電器的開關實作的，而現代電腦也是利用邏輯電路的通斷實作高低電壓來表示0和1。所以電腦內部的運算其實都是將其轉化為二進制再進行運算的。