828
劍指Offer之淘寶麵試題之小白鼠與毒藥解題過程分析
網上流傳著一題淘寶麵試題，原題如下：
我們有很多瓶無色的液體，其中有一瓶是毒藥，其它都是蒸餾水，實驗的小白鼠喝了以後會在5分鍾後死亡，而喝到蒸餾水的小白鼠則一切正常。現在有5隻小白鼠，請問一下，我們用這五隻小白鼠，5分鍾的時間，能夠檢測多少瓶液體的成分（）。A：5， B：6， C：31， D：32。
+1隻小白鼠首先可以想象隻有1隻小白鼠的情況，毫無疑問，1隻小白鼠五分鍾隻能判斷1瓶液體的成分，喝兩瓶或以上如果是碰不到毒藥，則喝多少瓶也能確定多少瓶；但如果遇到有毒藥的瓶子，則不能判斷那1瓶是毒藥，這樣的檢測是不合理的。- 死亡代表液體是毒藥
-
正常代表液體是蒸餾水
-
結論：1隻小白鼠可檢測1瓶液體成分。
+2隻小白鼠
兩隻小白鼠可以檢測3瓶液體成分。從本節開始我們把小白鼠標號N1,N2。首先根據前述結論可知N1,N2小白鼠各喝1瓶液體（N1:1號液體，N2:2號液體）則能夠準確判斷2瓶液體成分。但是第三瓶的判斷可能需要大家稍微轉點彎。因為采用的是每個老鼠獨立測試液體的方式，每個老鼠的死活並沒有任何關聯，每個老鼠測試的結果也就無法跟另外的老鼠測試的結果關聯。這樣做是一般做法，但有沒有可能把老鼠聯合起來測試來增大測試範圍呢？其實是可以的，那就是再拿一瓶3號液體讓N1,N2都喝一點。這樣有如下
-
喝法（縱向表示液體瓶編號，橫向表示小白鼠編號，交叉部分表示小白鼠是否喝了相應的液體）：
| 液體\小白鼠 | N1 | N2 |
| 1 | 喝 | |
| 2 | 喝 | |
| 3 | 喝 | 喝 |
-
死法（縱向表示N1小白鼠的測試結果，橫向表示N2小白鼠的測試結果，交叉部分數值是毒藥瓶編號或無毒藥。）
| N1\N2 | 死 | 活 |
| 死 | 3 | 2 |
| 活 | 1 | 無 |
-
結論：2隻小白鼠可檢測3瓶液體成分。
+3隻小白鼠由上一節的思維方式，我們可以想象3隻小白鼠是否能測試遠比3瓶或4瓶更多的液體成分呢？思考2隻小白鼠的測試方式，大家有沒有注意上麵采取的方式是N1,N2各喝了1瓶不一樣的（N1:1、3號液體，N2:2、3號液體）。我們除了讓每隻小白鼠單獨喝1瓶不一樣的液體，另外讓N1，N2同時喝了1瓶一樣的3號液體。同樣，我們可以對3隻小白鼠各自喝1瓶不一樣的液體後，在3隻小白鼠再喝第4瓶一樣的液體。測試如下：
順推思維
-
喝法（縱向表示液體瓶編號，橫向表示小白鼠編號，交叉部分表示小白鼠是否喝了相應的液體）N1喝1號4號液體;N2喝2號4號液體；N3喝3號4號液體。
| 液體\小白鼠 | N1 | N2 | N3 |
| 1 | 喝 | ||
| 2 | 喝 | ||
| 3 | 喝 | ||
| 4 | 喝 | 喝 | 喝 |
-
死法
- N1活N2活N3活：1、2、3、4號液體均正常。
- N1活N2活N3死：1、2、4號液體均正常，3號液體有毒。
- N1活N2死N3活：1、3、4號液體均正常，2號液體有毒。
- N1死N2活N3活：2、3、4號液體均正常，1號液體有毒。
- N1死N2死N3死：1、2、3號液體均正常，4號液體有毒。
-
注意，這裏不會出現有2隻小白鼠死了另外1隻活著的情況，因為隻有1瓶液體是毒藥，而且我們給3個小白鼠喝的方法隻有2種：單獨喝某1種液體，集體都喝某種液體。
-
結論：3隻小白鼠可檢測4瓶液體成分。
-
思考：通過如上結論大家有沒有覺得怪怪的，或者是不甘心。
- 1隻小白鼠測試1瓶液體
- 2隻小白鼠測試3瓶液體
-
3隻小白鼠測試4瓶液體，根據學數學的增量直覺，是不是太少了？或者如上方法是否有值得發散思維的地方？
發散思維關於上麵順推思維的解決方案，好奇的人就會問可不可以也讓3隻小白鼠也像2隻小白鼠測試的那樣兩兩都再喝1瓶一樣的液體呢？這樣又增加了3瓶（N1、N2再喝5號液體，N1、N3再喝6號液體，N2、N3再喝7號液體）。是不是就出現如上提到的2隻死亡其領外1隻活著的情況了？試想如果5號液體是有毒？或者6號液體有毒？7號液體有毒？這樣3隻小白鼠就能檢測7瓶液體成分了。仔細想想之後你會發現這樣是可行的。測試情況如下：
-
喝法（縱向表示液體瓶編號，橫向表示小白鼠編號，交叉部分表示小白鼠是否喝了相應的液體）
| 液體\小白鼠 | N1 | N2 | N3 |
| 1 | 喝 | ||
| 2 | 喝 | ||
| 3 | 喝 | ||
| 4 | 喝 | 喝 | 喝 |
| 5 | 喝 | 喝 | |
| 6 | 喝 | 喝 | |
| 7 | 喝 | 喝 |
-
死法
-
- N1活N2活N3活：1、2、3、4、5、6、7號液體均正常。
- N1活N2活N3死：1、2、4、5、6、7號液體均正常，3號液體有毒。
- N1活N2死N3活：1、3、4、5、6、7號液體均正常，2號液體有毒。
- N1死N2活N3活：2、3、4、5、6、7號液體均正常，1號液體有毒。
- N1死N2死N3死：1、2、3、5、6、7號液體均正常，4號液體有毒。
- N1死N2死N3活：1、2、3、4、6、7號液體均正常，5號液體有毒。
-
N1死N2活N3死：1、2、3、4、5、7號液體均正常，6號液體有毒。
-
N1死N2死N3死：1、2、3、4、5、6號液體均正常，7號液體有毒。至此，所有可能情況已經被枚舉完畢。
-
結論：3隻小白鼠是可以檢測7瓶液體成分的。
通過上述分析和思考，想必大家都很想知道這裏的原理和推論了。我們把剛剛得到的結論再次貼出：
-
- 1隻小白鼠測試1瓶液體
- 2隻小白鼠測試3瓶液體
- 3隻小白鼠測試7瓶液體
- 4隻小白鼠測試N瓶液體?
-
5隻小白鼠呢？
-
- 1隻小白鼠測試21–1瓶液體
- 2隻小白鼠測試22–1瓶液體
-
3隻小白鼠測試23–1瓶液體
其實總結起來大家會發現，我們采用了如下策略進行測試：
-
- 讓N隻小白鼠每1隻喝單獨的1瓶
- 讓N隻小白鼠任意中2隻再同時喝1瓶新液體
- 讓N隻小白鼠任意中3隻再同時喝另1瓶新液體
- 。。。
-
讓N隻小白鼠任意中N隻再同時喝1瓶格外新的液體
接下來考驗你數學功底的時候到了。
集合論學習比較過關的人會從上麵總結出N個小白鼠可以測試液體瓶數為：Cn1+Cn2 + Cn3+…+ Cnn-1+Cnn
如果你集合論的公式不是很熟悉又比較懶，又稍有耐力，那你可以慢慢計算出當小白鼠數量N=10時的結果是1023.但是多了你就不想在浪費時間了。
現在想想另外一個問題：一個包含N個不同元素的集合包含的子集合總數是多少（空集合也是集合）？
查看高2（2004年）數學書你就知道：總數=Cn0+Cn1+Cn2 + Cn3+…+ Cnn-1+Cnn 。即從中取出0、1、2...3、N-1、N個元素組成的子集合的總數。並且這個問題還有一個很簡單的解答方式： 設想其子集合很多，但是每個集合對於元素的包含隻有2種可能：包含、不包含。那麼N個元素的組合可能即2*2*2*...*2=2n
再來對照上麵的N個小白鼠測試液體瓶數：Cn1+Cn2 + Cn3+…+ Cnn-1+Cnn= （Cn0+Cn1+Cn2 + Cn3+…+ Cnn-1+Cnn ）-Cn0
即2n- Cn0。即2n - 1.至此
本題答案5隻小白鼠能測試的液體瓶數25 - 1=31已經解答完畢了。
======================================================================================================
總結回頭想想這個題目，因為隻有5小白鼠個，其實可以完全憑著你的發散思維和堅持不用靠集合論等高中以上數學知識搞定的，前提是你足夠會發散思維，會總結，推理能力較強。問題的關鍵處有3個，前2個能幫助你解答本題，後1個能幫助你做出總結和快速算法推論：
- 2個小白鼠能想到同時再喝1瓶新的。
- 3個小白鼠能想到分組在喝，多個小白鼠思考能有條不紊、不亂。
- N個元素集合子集數量的兩種表示法和證明過程
最後更新：2017-04-03 12:55:39