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

01-01

之前問了個1桶有毒的問題，後來考慮如果不只一桶毒酒的情況。兩桶毒酒我自己算了一會要比1桶的情況難很多。
用資訊理論的方法(感謝 @zhiqiang 大神的博文），下界應該是 log_5(1000*999/2),理由是共有1000C2種可能出現毒酒的方式，然後每頭豬身上最多可以有5種信息表達方式(前15分鐘死，30分鐘死,etc) 但我目前的困惑是找到下界後需要讓這幾頭豬做什麼才能測試出來或者說下界一定都是可構造的嗎?如果可以該如何構造？

我沒辦法證明這個下界做不到，但是事實上可能會很困難吧，和具體的問題的結構有關。

舉個例子，反過來說，1000桶水中有999桶毒水，1桶無毒，最少多少頭豬能找到這桶無毒的水？1桶無毒和1桶有毒，信息量其實是一樣的，但這時候之前的辦法就完全不適用了。

一般來說，我們能用信息量來證明多少多少不行。但是要詳細論證多少多少可以，可能一般來說是非常困難的，比如要考慮具體的問題。

這個問題的本質就是資訊理論里信源編碼，或者叫數據無損壓縮。這裡就是相當於用五進位碼做壓縮。壓縮的極限（下界）是熵，最優的壓縮方法比如 Huffman code 是可以構造出來的，不困難，對這題會比較繁瑣。但是最優壓縮辦法也不一定能達到熵值。另外可以證明，最優的壓縮辦法雖然可能達不到熵，最多也就多用一頭豬。

證明下界（熵）能否達到也不困難。假設我們要編碼一個在{1, 2, ... M} 內分布隨機變數X（不一定均勻分布）。假設 X 在數字 i 上的概率是 p(i)。那麼資訊理論里有定理說：當且僅當 p(i)=d^{-m(i)} 的時候（這裡d 是進位數，這題就是5，m(i) 都是正整數），最優編碼方法可以達到熵值。對於這題，p(i) 當然都不是這個形式，所以下界達不到。

借鑒@朱涵俊的思路。如果對了更好，錯了就當提供個錯誤典型吧。

答案是9頭。

第一次分9等份給豬喝。

兩種情況：

（1）死一頭。考慮糟糕情況，即兩桶都在這已知的ceil(1000/9)=112桶中。

分8等份，剩下8隻繼續喝，之後就簡單了。

（2）死兩頭。那麼問題退化為：4隻豬用3次判斷112桶。4^4=256&>112。

更正：經評論區指出。（2）的情況應為3隻豬。4^3&<112。因此此方法有誤。

更新：（2）的第二次，有一隻當兩隻豬使，兩邊各喝112/4=28桶，這樣是不是就對了？好像還是不對。

不過4^7&>112*111呀，然後怎麼做呢？

剛剛被感謝了，因此更新一下。這個問題已經被解決了，請大家看這個回答：

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

謝邀，最少需要8頭豬，如果想要100%沒有誤差的情況找出毒水數量，那麼最少需要13頭豬

毒水15分鐘發作，並且最多四次找出。

等分查找毒水，存在兩種情況：

1、每次都死一頭：那麼需要8隻豬即可

首先將1000桶水分成5份，最後一步分成4份，每份各200桶，會死一或二頭豬，每次分都是一到兩頭豬，每次均按最少的一頭豬算，即每次都能把兩桶毒水分到一組的情況，則:

豬數量為5+1+1+1=8

2、運氣較差的情況：死兩隻豬

先將毒水分成9份，最多數量為112桶,死兩隻，餘7，最壞情況為3隻豬3次機會判斷112桶水，並且有一隻豬可作為補足,7-3*2=1,無果，需要補足豬數量，

如果是5隻豬查找112桶水數量，則剛剛好可以找出毒水，所以所需豬數量為：

9+4=13

先直觀來計算下，2桶毒酒有1000×999種組合，需要lg999000/lg5=9頭豬檢查，但是每次檢查要2頭豬，2頭豬吃組合裡面的全死才算死，18頭肯定夠。但這個檢查有很多信息冗餘，2頭豬分別吃2份，應該有4種狀態，這裡只用了一種狀態，其他3種狀態沒有利用。

下面看看能不能少於18頭。

假設x頭豬，第一次分x等份喝，要麼一隻豬死，要麼2隻死，如果2隻，退化為一桶有毒問題。lg（N/x）/lg（4）=（x-2）/2，除是因為2個組都有一桶有毒，需要2份。減2是因為第一次死了2隻。是本來5種狀態，現在第一步篩選去掉一個狀態。

假設第一次只有一頭豬死，繼續上一步篩選。

假設每次篩選都是1頭豬死，那麼需要x頭，1000/x/（x-1）/（x-2）=x-1，因為假設5隻桶2隻有毒，只要4隻豬就夠了，有一個桶是可以不喝的。答案是7頭。

那麼來倒推下上面有2頭豬死的情況，如果用7頭豬，第一次篩選出2個143桶有毒，143桶選一個是lg143/lg4=4，2個143需要幾頭呢？肯定不超過8頭。加上第一次死的2隻，需要10隻。開始按7頭估計的，那麼應該是8-10頭。按8，9重新計算，也是需要10隻。

那麼再來推算下第一次1隻死，第二次2隻死的情況。第一次找出1000/10=100桶，裡面2桶有毒，第二次2堆100/9=12個桶，各有一個有毒。lg12/lg3=3，2組需要6隻，而經過前面2次死3隻，還有7隻，足夠了。

可以繼續推算第一次1隻，第二次1隻，第三次2隻，第一次100桶有2隻，第二次12桶里有2隻，第三次2堆2隻桶，各有一個有毒，這時候還有6隻豬，足夠區分了。

因此10隻肯定可以。

2組143，每組裡面各一個有毒，上面是按8隻算的，應該還能減少。

弱雞強答一波沒有資訊理論拋磚引玉。

假設毒性是 1比1000 混合都能導致豬在15分鐘內死亡。（為什麼這麼假設呢？因為如果毒性可以被大量的水稀釋的話，我tm就沒必要找出這1桶水了，直接稀釋所有的水一頭豬都不會死多好）

1桶有毒的情況

隨便亂湊

直接給結果是需要使用8頭豬喝水22次，4隻死亡的代價。

分4次 6*6*6*5=1080

每批對應一頭豬次（豬次一頭豬喝一次水）

第一次分成6批每批167桶

第二次分成6批每28桶

第三次分成6批每5桶

第四次分成4批每1桶

會死多少頭會死4頭，每次只死亡1頭。

這裡是需要用8隻豬參與喝水。

更新：評論區點出了兩桶的問題所在。而且自己還發現了只算了參與喝水的豬次，沒算死亡（損失豬次）已補充並修改。

確實疏忽大意了啊沒多想

我只想給出個確切的答案而已，腦子裡面隨便想了兩下得出了個結果和分發，自然談不上科學，也談不上最優解。請摺疊我+沒有幫助吧。

那麼兩桶的話。涉及到二次拆分。略微複雜了一點。

需要在後續再次細分一下。

話說突然發現題目裡面有個至少嗎？至少一頭（運氣好的話，哈哈）。

反之大多數有毒的情況這就難了，非要用豬來實驗，感覺只能用999頭豬獻祭了。

最少需要7頭豬(具有很大偶然性)，在保證一定能夠找出兩桶毒水的情況下，應保證有14頭豬。

毒水15分鐘可致死，要求我們最多用四次找出。

1000桶水先五等分，最後一步四等分(四等分也行，不過要從第二步再開始五等分，區別不大)，每份各200桶，每桶各取一點水混在一起餵豬喝下，會死一或二頭豬，每次分都是一到兩頭豬，每次均按最少的一頭豬算，即每次都能把兩桶毒水分到一組的情況，則:

1000分五組(五頭豬)，死一頭，分出200桶水，200分五組(再牽一頭補足五頭，此時實用豬六頭)，死一頭，分出40桶(再牽一頭補足五，此時實用豬七頭)，再死一頭，分出八桶，此時還剩四頭豬，將剩餘八桶水四等分，找到兩桶毒水。

用時正好一小時。

這是最偶然的情況，再另一個極端情況，即每次都是死兩頭豬的情況。

首先十等分，1000分十組，死兩豬(剩八隻)，分出200桶水，十等分(牽2頭補足，實用豬12隻)，死兩豬，分出40桶，此時剩八隻豬，再十等分(牽兩隻豬補足，實用豬14隻)，死兩豬，剩八豬，分出8桶，得出兩桶毒水。

用時一小時，總用豬14隻

數學下限在這種模糊的問題下面沒法確定。比如豬喝多久(或多少劑量)才會在最長的15分鐘內死亡？一種假設是，豬喝一秒的劑量會致死，而且恰在15分鐘的時候。這樣答案是兩頭，15*60s=900,也就是說一頭豬可以驗證900桶水，時間(秒)就是桶的編號！

兩頭。一頭從頭開始喝，一頭從尾開始喝，每隔1s喝一桶，通過死亡時間-15分鐘再除以1/60分鐘就可以推斷出是哪桶水了。

同理，如果有x桶毒水，則需要2^（x-1）頭豬。隨便選個不重複桶往首尾釋放小豬豬開喝就行了。