1000桶水中兩桶有毒，豬喝毒水後會在15分鐘內死去，想用一個小時找到毒水，至少需要幾隻豬？如何實現？

12-04

限制條件：
1.毒水劇毒，只要喝了就一定會在15分鐘內死，死亡時間不固定。
2.不考慮標記，安排，或喝水的時間。

相關問題：1000桶水，其中一桶有毒，豬喝毒水後會在15分鐘內死去，想用一個小時找到這桶毒水，至少需要幾隻豬？ - 知乎

我有一種用10隻豬的方法:
1.給每隻豬喂對應個位數編號的水，這樣第一個15分鐘後肯定最多死兩隻豬。
2.1.如果死了兩隻豬的話，則同時確定了兩個一百桶水裡有一桶水有毒。問題簡化成一百桶水裡有一桶有毒，試45min確定哪一桶。將剩下八隻豬平均分開，利用鏡像問題 @Sun AO 提供方法(即用幾進位的四位數至少可以表示到100)，分別確定這桶水。因為4*4*4*4&>100。兩步一共需要10隻豬。
2.2如果僅死一隻豬的話，問題變成100桶水裡兩桶有毒，45min確定哪兩桶。利用1思路，給剩下每頭豬喂9餘數的水。

2.2.1若死兩隻豬（此時還剩下7隻豬），則問題簡化成12桶水一桶有毒，試30min確定。將剩下豬分成33兩組。因為3*3*3&>12。

2.2.2若死一隻豬（此時還有八隻豬），問題變成12桶水裡一桶有毒，30min確定哪兩桶。利用1思路，給剩下每頭豬喂8餘數的水。

2.2.2.1若死兩隻豬（此時還有六隻豬），問題變成2桶水裡一桶有毒，15min確定哪兩桶。
2.2.2.2若死一隻豬（此時還有七隻豬），問題變成2桶水裡一桶有毒，15min確定哪三桶。

故而此方法10隻是最多的。

PS.這個問題需要找到一個平衡點:在哪一步確定出剩下的水裡面肯定有且僅有一桶有毒。因為確定一桶水的位置的速度是冪數級的，而將水分開的速度是階乘級的，所以越早分開越好。
顯然每次死兩隻豬的過程是最浪費的。所以上限應該取決於此過程。
如果是九隻豬的話，剩下2個112桶水被確定有且僅有一桶毒水。將豬按3隻和4隻分開。但3隻豬最多只能表示3*3*3*3=81隻。

基此方法可以一勞永逸地解決n桶水裡有k桶有毒，t時間內確定出來，至少需要l只豬的問題。

不過根據理論計算:1000桶水裡兩桶有毒一共有499500個狀態。而每隻豬一個小時內共有5個狀態（15 30 45 60min內死和不死），l只豬一共就有5^l個狀態。即5^l&>499500。l&>8.15。也就是說有種方法可以只用九隻豬。這種方法是基於將水兩兩組合，給每個組合編號，然後用5位l進位數去表示這些組合。
但是我覺得這個理論值偏低，因為對於豬而言分不清究竟是一桶水毒死自己還是兩桶？所以1000桶水兩兩混合之後，有毒的組合有1999種。問題轉化為499500桶水裡有1999桶有毒，試一小時確定，使得問題反而複雜了。

至少需要九頭豬，本題可以用兩種方法去解決

第一種方法，是分叉進位法，就是前期分叉法，後期進位法。用這種方法解決10頭豬難度不大，嘗試用9頭豬的話，難度大約是10頭豬的五倍以上，過程比較複雜。

分叉進位法可以參照我對一頭豬回復用的第三種方法，1000桶水，其中一桶有毒，豬喝毒水後會在15分鐘內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？先用分叉法，再用進位法。進位法由於提供信息窮盡最大化，對兩頭豬在一個區間的情況會無法區分，所以思路是在確定兩頭豬在不同區間，才能用進位法。
會出現兩種情況，就是一頭豬死還是兩頭豬死，一頭豬死意味著的情況下，就繼續分叉，假定一直是一頭豬死，8*7*6*5＞1000，那隻需要八頭豬。但兩頭豬死的情況下，在哪一步死掉有區別的。計算可以得出，第一步分叉最不利。
這種情況下，10*4*4*4*4&>1000,用十頭豬可以解決。

如果用9頭豬就是9*3*3*3*3＜1000，不夠用了。
但可能並不意味著十頭就是最優解，進位法的本質是用交叉的情況來進行判別，9*3.5*3.5*3.5*3.5＞1000，所以用九頭還是有理論上的可能。只是難點在於如何找到合適的交叉方式。

下面就嘗試九頭豬的解法。
由於3.5比較麻煩，所以最好能有個方法能讓它變成整數，一個方法是平衡分叉法和進位法。

六隻豬一輪區分兩杯毒水極值是7

七隻豬兩輪區分兩杯毒水極值是4*7+3=31

可以理解為分成7份4加一份3,7頭豬驗證4，1頭豬死，就用6頭豬一輪驗證7，兩頭豬死，就用5頭豬1輪驗證4和4.

八隻豬三輪區分兩杯毒水極值是3*3*3*8+（31-3*3*3）=220

不過這8頭豬三輪區分兩杯毒水的極值220是在無任何其他信息的基礎上。根據@keghost 的計算，在考慮最早一輪的結果的時候，比如某區域至少有一杯毒水的情況下，還有可能擴大的，但這個數字需要考慮以下的數字：兩杯毒水分開在兩個區間，七頭豬三輪能驗證的極限A。根據後來的計算，這個A如果為112，那麼八頭豬三輪的區分兩杯毒水的極值還能變成227.詳細可以見他在回復中的回答。當然這個227也是考慮112的結果，如果設定A為96，大概可以得到的極值是233。

將1000分成9個98和一個118。喂每頭豬98，會有兩種情況：
第一種，一頭豬死，將98+118=216，問題變成用八頭豬區分216中兩桶水的問題。用分叉進位法，分成八份27，兩隻豬死，3*3*3=27正好解決問題。一隻豬死，轉化問題是七隻豬兩輪區分出27。問題可以解決。

第二種，兩頭豬死，問題就轉變為，兩個98中各有一桶毒水，七頭豬三輪驗證。以下將嘗試各種方式。

嘗試一

將每個98都分成81和17。每個81分配三頭豬用進位法，然後用剩餘的一頭豬兩輪依次去喝兩個17。

如果沒死，問題就變簡單了。直接得到答案。

如果死了，則調用相應三頭豬過來驗證。用這個方法計算七頭豬可以得出的極限是

3*3*3*3+2*2*2=89，不到98。所以應該嘗試別的方法。

嘗試二

一個分成81和17，三頭豬嘗試進位法，第二個三頭豬嘗試第二個98用的是三個24，多餘的豬去驗證第一個17。只要17和24不同時死就能解決問題。但最不利的情況是17死，24死一個。剩餘五頭豬，在24和17中兩輪找出答案。用3頭豬兩輪找出24，兩頭豬兩輪只能確定9。

答案是81+9=90&<98

至此，仍然沒有得出答案,陷入困境。

但感謝 @keghost ，在回復中，很巧妙地改進了方法，得出以下的嘗試

嘗試三

該方法由@keghost 提供， @geo geo 也在討論中提供了幫助，回復中原文：

按第一種方法，7頭三輪99/108可以解決。99分成6個9，6個3，1個27；108分成27+81，27由7號豬試。
6個9各1頭，1-6號豬，6個3分別由1和2、2和3、3和4、4和5、5和6、6和1公用。
不死，27x81，7頭2輪可解決。
只死1-6號，9x81，6頭2輪可解決。
只死7號，27x27，6頭2輪可解決。
死2頭的情況。
1-6號死2頭，3x81，5頭2輪可解決。
1-6死1，7死，9x27，5頭2輪可解決。
死3頭的情況。
1-6死2，7死。3x27，4頭2輪可解決。
所以第一種方法可行。

在這個嘗試三方法的基礎上，由於組合可以提供更多的信息，所以我把方法再改進一下，得出以下的方案：

嘗試四

有兩個108，一份108分成6個8和15個3和15個1，另一個108仍然分成4個27。然後用6頭豬去嘗試8，1頭豬去嘗試27。然後6頭豬進行組合，理論上提供6*5/2=15種組合方式。用6頭豬進行33組合，理論上有6*5*4/(3*2)=20

用這15種組合方式去嘗3.

用33組合中的20個組合中隨機選15個來嘗1

之後的解決方法和嘗試3比較類似，不詳細說

如果出現左邊3頭豬同時死的情況，則可以直接確定1，問題變成4頭豬找出81或者3頭豬找出27.

理論上，單邊的上限是6*9+15*3+20+27=146&>108,取為108

該嘗試四的方法目前所能得出的上限是108&>98,問題可以解決

本以為108可能是極限，但隨後發現了仍然有更好的方法。

嘗試五——目前最好的方法

有兩個112，一份112分成5個9和10個3和10個1和1個27，另一個112仍然分成2個27，1個58.然後用5頭豬去嘗9，2頭豬去嘗2個27。然後5頭豬進行組合，理論上提供5*4/2=10種組合方式，這10種去嘗3。用5頭豬進行33組合，理論上有5*4*3/(3*2)=10，這10種去嘗1.

這種情況下，是上面方法的升級版，對另一邊進行了改造。理論上另一邊的上限是144&>112

至此結論九頭豬可以驗證出來，9頭豬驗證的數量為：112*8+227=1123。

如果有可以突破112的方法，歡迎一起探討。

由於情況比較複雜，每一步細部都可以寫得比較長，過程寫得簡略，能看懂的都是聰明人！

第二種方法是純進位法。

進位法的本質上是多維度交叉的方法，即每一個位數都與其他位數完全獨立，卻又必然有重合的地方。很直觀的類比是魔方，魔方就是三維交叉，對應進位法是三位數的任意進位。每個平面都與其他兩個維度的平面垂直相交。

3*3*3的魔方中，一共有27個方塊，假如有1個方塊是特別的，那麼這個方塊對應三個穿過它的平面。只要確認這三個平面，找到交叉點就可以找到這個方塊。所以可以嘗試用的方法是，派三頭豬挨個檢驗，依次檢驗上下，左右，前後。檢驗兩輪可以得到結果，因為比如你在上下方向的第一排沒有，第二排也沒有，第三排就可以不用檢驗了，可以直接推理在那邊。這就是一桶毒水進位法的類比。

假如現在3*3*3的魔方中，有兩個方塊特殊的，那麼這個方塊對應著兩組三個穿過它的平面。假如上下方向依次在第一排和第二排，那麼假如你用一頭豬檢驗第一排，那麼這頭豬死了你知道在第一排里有，但此時尚不知道第二排第三排的情況，這個時候你需要再派一頭豬去檢驗第二排，如果第二排沒有，下面可能有兩種情況，一種是兩個特別方塊都在第一排，也有可能一個在第一排，一個在第三排，所以仍然需要去檢驗第三排。這就意味著上下，左右，前後每個維度搜尋需要的豬的數量是兩頭，需要兩輪。這就是兩桶毒水時候使用進位法的不同之處。

那麼使用進位法來解決1000水的問題，需要確定的是兩點，首先到底是用幾進位，其次是需要多少頭豬。

用幾進位主要取決於兩頭豬四輪可以最多在幾桶毒水中，找到兩桶毒水。之前之所以採用五進位，是因為當有一桶毒水的時候，1頭豬在四輪之內最多找到5桶毒水中那一桶，如果6桶的話，就找不到了。那麼兩頭豬兩桶毒水的時候，想像把毒水排成一排，兩頭豬挨個從兩邊開始找，四輪，理論上最多可以搜尋8個，那麼是8進位嗎？不是的，因為最不利的狀況是有1頭豬第一輪就死了，而第二頭豬遲遲沒死，假如毒水在第一排和第二排，那麼從第一排開始的一開始就死了，第八排開始的豬只找到第五排就結束了，第二排沒有檢驗。因此兩頭豬兩桶毒水，可以確保能找到的排數仍然是5排。所以仍然用五進位。

所以用十頭豬的時候，答案是一樣的，5^5&>1000，可以解決問題。

用八頭豬的時候，5^4=625&<1000，不可以解決問題。

比較有趣的是9頭豬的情況，那麼如果是9頭會怎麼樣了。9頭怎麼使用進位法，這需要一個比較巧妙的方式。

我們設想，由於每位需要兩頭豬，9頭豬的情況下，最多仍然是四位數，不可能到五位數。但進位數可以發生變化。

我們想像9頭豬分成四份，每一位可以有2.25頭豬去檢驗，那麼這個0.25有什麼用？在應用中，可以把多餘出來的那頭豬依次去幫助每一位的兩頭豬去檢驗一排，四輪正好可以幫助四次。如果這頭豬在檢驗中死了怎麼辦，那也不要緊，直接讓該位沒有死掉的一頭豬去代替這個多餘的豬的職責。

這樣，每2.25頭豬，四輪可以找到的排數是5+1=6，比如多餘的豬和兩頭豬一同檢驗第一位，兩頭豬檢驗1,5，多餘豬檢驗6，如果多餘豬死了，1,5最多死一個，如果死一個，兩桶毒水的排數已經確定，還剩一頭，可以代替多餘豬去檢驗其他排的6。這樣進位數可以升級到六進位了。

這樣9頭豬使用的計算方法是：6^4=1296&>1000

關於該方法有一點需要注意，每一位並不需要進位數是一樣的，本題9頭豬時候，恰好四位都是6進位，這是巧合，其實並不一定需要，比如只讓多餘豬在第一位，第一位有三隻豬，四輪至少可檢驗的數量是9排，還可以用的方法是5*5*5*9=1225&>1000,同樣可以解決問題，但根據數的計算定律，總和一定的時候，平均分配時候的乘積是最大的。所以最終表達的其實不是數字，進位只是幫助理解，本質上只是各維度的交叉，所以該方法用維度法稱呼其實更精確。

經提示，這第二種方法可以的確可以找出豬的坐標，但無法提供組合信息，所以最終無法確定是哪頭豬，所以各位看看是否有可能改進。

原來設想用一開始就使用交叉組來實現，但情況太複雜，反而不好處理。
但是在第一輪獲得信息之後，使用交叉組是可以提高上限的。
@小河流
你的第一種方法是可行的。
7頭3輪檢驗兩組時，每組的上限是可以提高的。
每組可以99，一個組可以108。
99分成6個9，6個3，1個27；
108分成27+81，27由7號豬試。
6個9各1頭，1-6號豬試；
6個3分別由1和2、2和3、3和4、4和5、5和6、6和1共試。
不死，27x81，7頭2輪可解決。
死1頭的情況:
只死1-6號，9x81，6頭2輪可解決。
只死7號，27x27，6頭2輪可解決。
死2頭的情況:
1-6號死2頭，3x81，5頭2輪可解決。
1-6死1，7死，9x27，5頭2輪可解決。
死3頭的情況:
1-6死2，7死。3x27，4頭2輪可解決。
最多死3頭。

經過嚴格計算，8隻不夠(390625)，9隻信息過剩(1953125)。因此答案是9 。

啊呀，我把回答寫到了1桶水問題中，我有個多桶水的解決方案，正好是作業，引用一下吧：

問題是：

假設給了a桶水，其中b桶有毒，用多少只豬可以在15分鐘內測出有毒的b桶？

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

這個解決方案還需要完善。具體研究已經有不少了，如果有興趣可以搜索關鍵詞Disjunct Matrix和Non-adaptive Group Testing，這個應該算partially adaptive group testing了吧

首先把問題轉化一下。
1、一個豬在一小時內可以檢驗的水桶數量為5個：15分鐘死、30分鐘死、45分鐘死、60分鐘死、60分鐘不死；
2、兩個豬在一小時內可以檢驗的水桶個數為5^2=25個
圖示：
a豬
。。。。。
。。。。。
b豬。。。。。
。。。。。
。。。。。
3、1000桶水裡有2桶毒水，那麼需要檢驗的點位有 (999+1)*999/2=499500 個；
4、幾個豬在一小時內可以檢驗超過499500 個點位？

即求解5^n&>499500，n為正整數

lg49500/lg5≈8.15

則n=9

LS的答案只有一個很清晰啊那個一句話說香農的。

@MISS老楊2.1有問題，8頭豬分成兩撥，4頭豬三次測100桶水無法實現（100化為二進位有7位）

我的答案也是10頭。

第一次分10等份給豬喝：

1.1.死2頭剩8頭。毒藥在兩個100桶AB中：

2.1.AB均分4等份13，4等份12，AB混，給8頭豬吃：

3.1.死1頭剩7頭，在某一份13中：分為6等分2，再加剩餘1桶，給7頭豬吃：

4.1.死1頭不討論。

4.2.死2頭剩5頭，僅討論在兩個2份中，直接給5頭中的4頭豬吃即可，其他情況更簡單。

3.2.死2頭剩6頭，在某兩份13（A、B）中（其他兩份情況不討論）：AB都分5份2，1份3，AB相應混（3配2）給6頭豬吃：

4.3.死1頭剩5頭，在某3份中，簡單不討論

4.4.死2頭剩4頭，在某3和某2中（其他情況不討論），分別給4頭豬吃，剩1份不用吃，結束

1.2.死1頭剩9頭。毒藥在某100桶中：

2.2.分8份11,1份12給9頭豬吃：

3.3.死1頭剩8頭，在某12份中（11不討論），4個1,4個2份，給8頭豬吃

4.5.死1頭剩7頭不討論

4.6.死2頭剩6頭，僅討論在兩個2份中，直接給4頭豬吃即可。

3.4.死2頭剩7頭，在12份和某11份中（其他不討論），12份分為5個2份，兩個1份；11份分為4個2份,3個1份，AB配

4.7.死1頭剩6頭不討論

4.8.死2頭剩5頭，僅討論在兩個2份中，直接給4頭豬吃即可。

無毒的狀態是1000桶取998桶的組合，概率P1,而一隻豬的狀態是5種，概率P2＝0.2根據香農，-logP1/-logP2

12隻豬，

上面是推導過程。就這樣

x的n次方等於1000.n倍的x就是你想要的

9頭。

我先看了相關問題（就是只有一桶毒水那個）的高票答案，總結出了：
1. 下限的估算方法：每頭豬能提供一輪死/二輪死/三輪死/四輪死/存活五個可能狀態，因此需要log(5, 桶樣本數)頭豬，在該問題中為5頭，在本問題里為9頭。
2. 檢測流程：
1. 設有a0頭豬，將桶樣本編號，桶編號編碼為a0位5進位數。每桶編號編碼為0的位對應的豬喝該桶水，存活a1頭豬，毒水在死去豬對應位為0，其餘位非0的桶中（若a1=0，毒水可確定，下同）；
2. 重新編碼嫌疑桶編號為a1位4進位數，繼續讓0位對應豬喝對應水，觀察結果；
3. 重新編碼嫌疑桶編號為a2位3進位數，重複流程；
4. 重新編碼嫌疑桶編號為a3位2進位數，根據結果可定位毒水。

所以該題5頭豬可以檢測3125桶水，這題9頭可檢測1975桶里的兩桶毒水。
這題有兩桶毒水，可以看成桶樣本數為這兩桶毒水編號的組合，即500 * 999。操作時為每一種組合編號，如果一頭豬該喝（桶1, 桶2）組合和（桶2, 桶3）組合，那麼同時喝桶1，桶2和桶3就好，與上面流程一致。
如果時間改了為n回合（一小時就是4回合），修改初始進位數為n + 1即可。
流程倒推可知這方案是最優的，爪機不贅述。

錯了，組合出來有1999個組合有毒，不是一個。再想想

7頭豬就可以檢驗出1000桶水中哪一桶有毒。
1.將1000=142+143+143+143+143+143+143 7種組合，死掉1頭，剩6頭，用時15分
2. 143=25+25+25+25+25+18 6種組合，死掉1頭，剩5頭，用時15分
3. 25=5+5+5+5+5 5種組合，死掉1頭，剩4頭，用時15分
4. 4=1+1+1+1 用時15分，檢驗結束。