你只有 10 只小白鼠和一星期的時間,如何檢驗出哪個瓶子里有毒藥?
有 1000 個一模一樣的瓶子,其中有 999 瓶是普通的水,有一瓶是毒藥。任何喝下毒藥的生物都會在一星期之後死亡。現在,你只有 10 只小白鼠和一星期的時間,如何檢驗出哪個瓶子里有毒藥?
根據2^10=1024,所以10個老鼠可以確定1000個瓶子具體哪個瓶子有毒。具體實現跟3個老鼠確定8個瓶子原理一樣。
000=0
001=1
010=2
011=3
100=4
101=5
110=6
111=7
一位表示一個老鼠,0-7表示8個瓶子。也就是分別將1、3、5、7號瓶子的葯混起來給老鼠1吃,2、3、6、7號瓶子的葯混起來給老鼠2吃,4、5、6、7號瓶子的葯混起來給老鼠3吃,哪個老鼠死了,相應的位標為1。如老鼠1死了、老鼠2沒死、老鼠3死了,那麼就是101=5號瓶子有毒。
同樣道理10個老鼠可以確定1000個瓶子
1,把1000瓶標號:1,2,3,4,5,6...1000.
2,所有老鼠排列在一起組成一個2進位隊列: 0000000000
0代表不喝,1代表喝
3,0000000001代表第一瓶水被喝情況
0000000010代表第二瓶水被喝情況
0000000011代表第三瓶水被喝情況
0000000100代表第四瓶水被喝情況
...
1111101000代表第1000瓶水被喝情況
4,第7天,喝了毒藥的老鼠都死了,那個二進位隊列轉為為十進位就是毒藥的標號。
比如第3隻老鼠死亡,其他老鼠沒死,隊列為0000000100,第四瓶水有毒。
第1,5,6,8老鼠死亡,其他沒死,隊列為0010110001,第177瓶水有毒。
wtf?不是很簡單嗎?
把瓶子列出來1到1000。
老鼠從1列到10。
第一個老鼠去喝所有奇數瓶子(除以二餘數&>=1的)。
第二個老鼠去喝所有除以四餘數&>=2的瓶子。
第三個老鼠去喝所有除以八餘數&>=4的瓶子。
...
最後把死掉的老鼠加起來(如果第N個老鼠死了,則值2^[N-1])
得出的總和就是有毒藥的那一瓶。
每個老鼠都得喝500瓶左右,有點可憐。不管。
將10隻老鼠剁成餡兒,分到1000個瓶蓋中,每個瓶蓋倒入適量相應瓶子的液體,置於戶外,並每天補充適量相應的液體,觀察一周,看哪個瓶蓋中的肉餡沒有腐爛或生蛆。
這個問題下,大都是通過二進位編碼的方式解答。我換個思路,不用二進位,嘗試用邏輯分析的角度解釋。最後說明此解法和二進位編碼法的關係。
Q1:為什麼 10 個白鼠能分辨 1000 瓶液體?
(先假設老鼠喝毒藥之後立刻死,而不是一周後,稍後解釋原因)我們讓第一隻老鼠喝一點前 500 瓶液體,如果它死了,那麼毒藥就在前 500 瓶里。下面,將存在毒藥的 500 瓶一分為二,再拿一隻老鼠來試驗:我們再次精確把毒藥限制在 250 瓶中。繼續下去,每次取一半做實驗,我們將依次精確到 125 瓶(第三隻),精確到 62 /(或) 63 瓶(第四隻),31 / 32 瓶(第五隻),15 / 16 瓶(第六隻),7 / 8 瓶(第七隻),3 / 4 瓶(第八隻),1 / 2(第九隻,這次可能一舉就確認,如果恰好出現在只有 1 瓶的那個分塊中,饒過一隻可憐的小白鼠,否則就需要再實驗一次決定),1 瓶(第十隻)。
因為每次老鼠實驗都能排除一半的可能,因此,10 只老鼠,最多可以分辨 2^10 個可能,即 1024 瓶液體。
Q2:上面這個假設沒有考慮到「只能觀察一次」這個前提,即不允許我們每次實驗一下,觀察並排除一半,再循環實驗。用什麼方式讓這種分辨在一次觀察中就解決呢?
(考慮 3 只老鼠,8 (2^3) 瓶液體的情況)我們讓第一隻老鼠喝一點 1,2,3,4 前四瓶的液體;第二隻喝一點 1,2,5,6 瓶;第三隻老鼠喝一點 2,4,6,8 瓶。
一周後,假設發生:第一隻老鼠死了:毒藥在前 4 瓶( 1, 2, 3, 4);第二隻老鼠活著:毒藥在( 3, 4);第三隻老鼠死了:第 4 瓶。
這個方法本質是確保每隻老鼠能繼續細分上一隻老鼠的結果。即,第一隻老鼠幫我們區分出了是前四還是後四,下一次我們需要區分在毒藥在前四瓶中的前二還是後二(或者後四的前二還是後二)。在 Q1 立即死亡的假設中,我們在知道是前四還是後四之後,再讓下一隻老鼠實驗前四的前兩個或者後四的前兩個;但是在題設延遲死亡的假設中,我們無法立刻知道,那麼,乾脆就讓下一隻把前四中的前二,和後四中的前二都喝掉——這樣我們無論如何都能知道結果了。
Q3:推廣到更多毒藥要老鼠怎麼喝呢?
如題設,1000 瓶的情況,我們讓每隻老鼠都喝一半總樣本的液體,即 500 瓶。第一隻喝掉前 500 瓶;第二隻每隔 250 瓶喝接下來的 250 瓶,即 1 ~ 250, 501 ~ 750;第三隻每隔 125 瓶喝 125 瓶,即 1 ~ 125, 251 ~ 375, 501 ~ 625, 751 ~ 875;第四隻每隔 62 瓶喝 63 瓶(或每隔 63 瓶喝 62 瓶);直到第十隻,每隔 1 瓶喝 1 瓶,即都喝奇數(或偶數)瓶。
比如只有第 1, 2, 3, 4, 5, 6, 7, 8, 9 只死亡的情況(除了第 10 只其他都死了),我們能依次精確到毒藥存在於以下範圍的瓶子中,1 ~ 500, 1 ~ 250, 1 ~ 125, 1 ~ 63, 1 ~ 32, 1 ~ 16, 1 ~ 8, 1 ~ 4, 1 ~ 2, 2。得出第 2 瓶是毒藥的結果。
Q4:這和二進位的解法有什麼區別?
沒區別。二進位解法中,第一隻老鼠,即負責個位的那個老鼠,就是每隔 1 瓶就喝一個:因為二進位逢 2 歸 0;第 3 只老鼠,即負責百位的老鼠,每隔 2^(3-1) = 4 瓶喝 4 個:二進位百位隔 4 個保持一樣;第 n 只老鼠,即負責從各位數第 n 位的老鼠,每隔 2^(n-1) 瓶喝 2^(n-1) 個。其實和上述用邏輯的方式喝法沒有區別。
答案是有了,但是我想說一下解題思路。想法可能很幼稚,望各位專家不吝賜教。我認為不宜只把這當成一道有趣智力題。在它有趣的外表下,事實上是嚴肅的數學問題。
可能有人覺得,這多簡單啊,用0.2秒聯想一下卡諾圖(或者3-8解碼器),打個響指,答案不就出來了嗎?但是我想說,這是需要天才的。可我認為好的解題思路,是不需要天才便可解答的思路。換句話說,依賴於天才的解題方法不是個好的方法。再者,即便對於天才,我想剝清那靈機一閃的背後,意識的水面下龐大的無意識洪流,是以什麼為根據運行的。再延伸下去就要到很多大師都談到過的知識與靈感的大問題了,不展開了。
說得簡單點,我想回答的是,我沒想到這個方法,憑什麼他就想到。現在就來談談這個憑什麼。
首先,題目做了個巧妙的障眼,把1024改成1000。但根據經驗,還是不難想到,要用這麼少的老鼠分出這麼大的任務量,肯定有指數爆炸的功勞。或者說,把問題對數分解。從而不難想到2^10=1024這個數量關係。
為了問題更容易理解,不妨把問題做一個變形:
問題2:把原問題中的1000個瓶子改成8個瓶子,10隻老鼠改成3隻老鼠。其它一樣。
這樣,問題2肯定有了個解法。下面的問題是,這背後的數量關係的本質是什麼?
按照職業和個人知識背景的不同,不同的人可能有不同的聯想。如果你學過演算法,不難從原問題的2^10=1024數量關係中想到二分查找演算法思想。問題是這裡只有單步(一個單位時間,或一個指令周期)計算時間。沒錯,老鼠負責做測試,就是一個處理機,符合計算的本質。於是,為了問題易於理解,不妨進一步做一次變形:
問題3:把問題2中的3隻老鼠改成1隻老鼠,但是老鼠有3條命,並且時間限制從一個星期改成3個星期。其它一樣。
於是,成了一個典型的二分查找問題,2^10=1024這個數量關係依然適用。這是按照程序員的思維走到二分查找的。但如果你不是程序員呢?或者說,自然而然想到變換到二分查找,這和一步聯想卡諾圖(或3-8解碼器)有什麼區別呢?更甚,二分查找的本質又是什麼?為什麼不是三分?
首先,因為老鼠只能通過活蹦亂跳,或死翹翹,來報出編碼為0或1的實驗結果,所以查找中的「二分」,可以說是直接的。
再者,為什麼不是三分?
二分的本質在於,每次處理,都把問題規模降解為原來的1/2,這才是問題得以解決的關鍵!為何不是1/3?
楊振寧說:「對稱支配宇宙力量。」有一本科普書叫《可畏的對稱》。有一種世界通行的說法叫「一枚硬幣的兩面」。有一種學說叫辯證法。再說,連陰陽和諧都要出來了,打住。暫時還不用這麼玄乎。
為什麼不是1/3?因為如果是1/3,那麼在老鼠給出0或1的不同答案的時候,你如果幸運,就是把問題規模降為了1/3;如果不幸,就只降為了2/3。我們說,依賴於運氣的方法不是足夠理想的方法。如果可以依賴於幸運,那你為何不說原題的解法,靠純蒙就能做到?在命運之神的全力狙擊下,依然肯定能按期交付的方法,才是可控的方法,才是夠理想的方法。如果你學過演算法,可以知道這也是一種叫「隨機化演算法思想」的奧妙。而且和演算法研究中,關注於「最壞情況運行時間」的研究原則一致。所以二分。
那麼在二分查找的背後,又是怎樣的規律?
基於測試(比較)的查找背後,是決策樹模型。如圖:
二分查找是以時間迭代來下降到決策樹的葉子;而在這裡的原題中只有單步的運行時間,卻有多個處理機,明顯是以空間迭代的方式下降到決策樹的葉子。學過演算法的又要說「Aha」了,「時間換空間,或者空間換時間」。事實上,這也是並行計算的思想。可以把這個看作是二分查找的並行實現。
如果你一開始想到的是邏輯門電路,那麼我想提醒數字電路的運行方式就是並行的。數字電路某種程度上就是並行機。
同時,這也是「量子計算機無法完成演算法之外的任務,卻可以把串列演算法,並行地實現」的真諦所在。
現在,問題2中,三隻老鼠同時單步內吐出0或1的答案。解的組合便是2^3=8,正好解決問題。
剩下的便是編碼了。0或1各代表什麼可以自定。因為只有0或1,二進位編碼是自然的,也是直接的。吐出0或1的是老鼠,所以明顯老鼠對應於一個二進位位(或稱一個bit處理單元)。3隻老鼠,3個二進位位。老鼠從低位到高位,編碼為:0, 1, 2。
3位二進位數夠簡單,所以先把所有數枚舉出來再說:
000=0
001=1
010=2
011=3
100=4
101=5
110=6
111=7
然後我實在抑制不住直接下一步跳入3-8解碼電路類比的衝動。但是我們再來問幾個為什麼。
注意到每個位,0和1各佔一半(這也是自然,窮舉了3位二進位數嘛),這和為了均等吐出0和1的可能性,需要的對老鼠的輸入是一致的。
(先爛尾到這裡,未完待續)
總之,10隻老鼠就像10根地址線,可以定址1024個瓶子(內存單元)。至於理由根據,筆者也暫時不清。筆者也無暇查看編址譯址電路的早期思想萌芽,產生於哪些論文中。筆者也隱約覺得應用信息熵的理論, 就可以理想地、「無需想像力」地、堅實地,一步解決。但其實信息熵的理論是什麼樣的,我也不太清楚,只是猜想。你問我為什麼不去學信息熵?也是因為懶啊。
怎奈學海無涯。
我的解法又簡單又好懂,各位看官請看:
思路:
利用二分法~(針對有評論說時間不夠的,其實是一瓶藥劑分很多份十個老鼠同時喝)
1000瓶子編碼1-1000.
第一天,第一隻鼠喝1-500,這樣結束時,他死了,則1-500有毒,沒死則501-1000有毒。
與此同時第一天,第二隻鼠喝1-250,501-750.方法同理。
與此同時第一天,第三隻如上,250除以2是125.
與此同時第一天,第四隻我就懵逼了。因為125不能被2整除。
傷心中……
然後我反過來從小往大推。
第一隻每隔1瓶喝1瓶,即喝1、3、5、7、9……
第二隻每隔2瓶喝2瓶,即喝(1、2),(5、6),(9、10)……
第三隻類推,每隔4喝4.
第n只每隔2^(n-1)喝2^(n-1)
也就是:
第十隻每隔512喝512。
因為512大於1000的一半,能涵蓋所有可能。
一周之後通過十隻小鼠的死亡可推理出哪一瓶是毒藥,所以方法可行。
得解。
(其實就是二進位演算法,因為這是正確解法,我只是把思考方式寫出來便於大家理解)
再次強調!評論里說我二分法時間不夠的真的不是在逗我嗎?第一天的時候,10隻可愛的小老鼠就已經都喝好葯了啊!哪裡時間不夠了?請告訴我,我好想知道!
我來用數學歸納法給個嚴格的證明。
問題可以描述為:有2的n次方個瓶子和n只老鼠,瓶子里裝的是水,有一個瓶子的水有毒,老鼠喝了後第7天會死,那麼在第7天能識別出這瓶毒藥嗎?
證明:
當n=1時,把其中一個瓶子的水給老鼠喝第7天能識別出毒藥。
假設當n=k時,第7天也能識別這瓶毒藥。
當n=k+1時,
假設瓶子的編號為1,2,3 ...直到 2的(k+1)次方。
將每兩個瓶子分為一組,並將這兩瓶水取一點出來混合,剛好可分為2的k次方個組(其中編號為 i 的瓶子和編號為 (2的k次方)+i 的瓶子是一組),。
那麼用k只老鼠第7天就能確定是那一組瓶子里有毒藥。假設最後結果是第m組有毒(即編號為 m 和 (2的k次方)+m 的兩個瓶子)。
同時將編號從 2的k次方+1 到 2的(k+1)次方 的瓶子(共2的k次方個瓶子)的水給第 k+1隻老鼠喝。
如果第7天第k+1隻老鼠沒死,可以得知毒藥在編號為 1 到 2的k次方 的瓶子中,由此可知是編號為m的瓶子有毒。
如果第7天第k+1隻老鼠死了,可以得知毒藥在編號為 2的k次方+1 到 2的(k+1)次方 的瓶子中,由此可知是編號為 (2的k次方)+m 的瓶子有毒。
因此n為自然數時,都能識別出這瓶毒藥。
以下給出用javascript寫的具體計算方案。(和上面證明方法不同的是程序中瓶子和老鼠的編號是從0算起的)
將以下&到&之間的代碼保存到一個新建的文件cacul.html中,並雙擊打開cacul.html,可以計算各種不同情況下得試驗方案。
&
&
&
&
以下是一些運行結果: