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

11-25

限制條件：
1.一滴毒水足以導致一頭豬的死亡。死亡時間為15分鐘內不確定的某個時間點。
2.其死亡只是毒水導致的，不會有其他因素導致死亡。
3.豬的承水量無窮大，且假設飲一桶花費時間為零。

相關問題:http://www.zhihu.com/question/19676641

相關題目:Poor Pigs | LeetCode OJ
抱歉題目這麼長，同學問我的問題
~~~~~~~~~~~~~~~~~~~~~~~~~~~
樓下 @Sun AO 同學的解答很完整。
有興趣的可以看看拓展問題：1000桶水，其中兩桶有毒，豬喝毒水後會在15分鐘內死去，想用一個小時找到這桶毒水，至少需要幾隻豬？ - 知乎

用資訊理論的方法求出至少是5，其他各種想找出5頭豬以下的人可以省點力氣。

在1000桶水中找一桶水，需要的信息量是-log(1/1000)。而一頭豬所能提供的信息是它在什麼時間死，因此能提供的信息量是-log(1/5)。4頭豬能提供的信息量是-4log(1/5)=-log(1/625)，不夠。5頭豬能提供的信息量是-log(1/3125)，剛好夠。

至於用什麼信息編碼方式就見仁見智了，樓上有的回答就很好。

這裡只是嚴謹地證明一下「至少」。

================= update 5.30 =================

1.評論中有回復說「豬會死」，好像是在說豬死了就得不到後面的信息了。其實可以設計演算法，讓豬在5個時刻中有且只有一個時刻會死。下面簡單說一下編碼思路：

（就用最簡單的坐標法，把題目簡化為25桶水用2頭豬的情況。）

兩頭豬可以表示的情況有(0,0),(0,1),(0,2)...(4,2),(4,3),(4,4)，也就是說每種情況要對應某桶水有毒。可以用z=x*5+y的編碼方式，z表示桶號碼，x表示餵給第一頭豬的時刻，y表示餵給第二頭豬的時刻。也就是說，第一頭豬0時刻喂的水為0,1,2,3,4；1時刻喂的水為5,6,7,8,9，以此類推。第二頭豬0時刻喂的水為0,5,10,15,20；1時刻喂的水為1,6,11,16,21，以此類推。這樣，如果豬在(i,j)點死，即第一頭豬在i時刻死，第2頭豬在j時刻死，那麼說明第(i*5+j)桶水有問題。顯然，豬如果在前四個時刻都不死，那一定會在假設的第五個時刻死。

（題目中1000桶水的情況可以將2維空間擴展成5維空間類似編碼）

顯然這樣的話豬必定在五個時刻中有且只有一個時刻會死，不會浪費信息。

2.有人說恰好第一頭豬第一個時刻餵了一桶水就死了，這樣立刻就能確定是哪桶水，所以「至少」是一頭豬。需要注意的是，「至少」指的是在任何情況下都要能夠確定出來，就像演算法的時間複雜度，指的是對任何情況都要在這樣的時間複雜度內解決問題。

================= update 5.31 =================

3.詳細解釋一下這裡信息量的含義。信息熵的計算公式為 $H=-Sigma_{i=1}^{n} p_i log p_i$ 。1000桶水中有一桶水有毒的情況有1000種，要麼是0號水有毒，要麼是1號水有毒。。。因為沒有先驗知識，所以只能假設每種情況等概率，用信息熵公式計算信息量就是 $H=- Sigma_{i=1}^{1000} {frac 1 {1000}} log {frac 1 {1000}}$ ,即log(1000)。

4.在實驗中，「豬死」不是意味著後面的信息就獲取不到，謝謝 @Sleor Chen 的評論，我5.30的更新欠妥。豬死的情況有5種，由資訊理論知識，等概率下信息量最大，最大信息量是log(5)約=2.3，(以2為底)。當然這就和實驗設計就有關係了，假如有一個極端的實驗，對某頭豬0時刻喂的水是0-995，1、2、3時刻喂的水分別為996、997、998，（假想的4時刻喂的水為999），那麼所得信息量就是 $H=- {frac {996} {1000}} log {frac {996} {1000}}-4*{frac {1} {1000}} log {frac {1} {1000}}$ 約=0.05，這樣的實驗設計就不夠好。因為它在後4個時刻都只喂一桶水，導致獲取的信息量很少。意思就是如果有毒的水在0-995之間，那麼你這次實驗相當於白費。所以在設計實驗時，就要盡量考慮到讓豬在這5個時刻喂水的數量平均，總共1000桶水每個時刻就喂200桶的混合，這樣獲得的信息量是最大的。一隻豬表示一個實驗，那麼一個實驗的信息量在設計時就已經確定了，與豬什麼時刻死無關。順便說一下，多隻豬為了能確定出更多信息，需要使各個實驗相互獨立(各實驗間互信息要小)。

================= update 6.07 =================

5.謝謝 @雲之君兮的評論，指出1000桶水即使有先驗概率也還是需要5頭豬才能確定。

我想5頭就夠了吧。

將1000桶水按5進位編號，因為5^5&>1000，所以每桶水的編號是一個五位數。將五頭豬對應到每一位。首先喂每頭豬5進位編號下該位數為0的水。15分鐘內，如果某頭豬死了，那麼有毒的水該位就是0；然後過15分鐘後，再喂還存活的豬5進位編號下該位數為1的水。15-30分鐘內，如果某頭豬死了，那麼有毒的水該位就是1。以此類推，於是在一個小時內我們就可以判斷有毒的水的編號在5進位下每一位是多少，從而找到這桶水。

我認為4頭及以下的豬是不太可能完成這個任務的。因為1個小時內每頭豬最多提供一下的信息：

0-15分鐘死/15-30分鐘死/30-45分鐘死/45-60分鐘死/不死。所以4頭豬最多表示5^4&<1000個可能的狀態。不知道有沒有更聰明的辦法用更少的豬解決這個問題。

===================================================

在這裡補充一個例子幫助大家思考這個問題：因為我們只在0，15，30，45分鐘喂水，所以我們將這幾個時間點記成第一二三四輪。5頭豬稱為1號豬2號豬3號豬4號豬5號豬。把1-1000號水按照5進位編號。

第一輪：喂1號豬5進位下末位數是0的水，喂2號豬5進位下倒數第二位數是0的水，喂3號豬5進位下倒數第三位數是0的水，喂4號豬5進位下倒數第四位數是0的水，喂5號豬5進位下倒數第五位數是0的水。

第二輪：開始前發現3號豬和5號豬死了。所以有毒的水的編號是0_0__. 喂1號豬5進位下末位數是1的水，喂2號豬5進位下倒數第二位數是1的水，喂4號豬5進位下倒數第四位數是1的水。

第三輪：開始前發現2號豬死了。所以有毒的水編號是0_01_. 喂1號豬5進位下末位數是2的水，喂4號豬5進位下倒數第二位數是2的水。

第四輪：開始前發現1號和4號還活著。喂1號豬5進位下末位數是3的水，喂4號豬5進位下倒數第四位數是3的水。

到60分鐘的時候，發現1號死了，4號還活著。所以有毒的水的編號是04013。這個數在10進位下是508，所以是508號桶水有毒。

5隻吧。

來來來讓我用初中生都能看懂的語言講一遍。

簡單的例子：兩隻豬，25桶水。將水桶（@）如下排列：

頭15分鐘：

第一頭豬喝位於（1，一）、（1，二）、（1，三）、（1，四）和（1，五）的水；
第二頭豬喝位於（1，一）、（2，一）、（3，一）、（4，一）和（5，一）的水。

換句話說，每個15分鐘內，兩隻豬分別喝一列水和一排水。

這樣，一小時後毒水的坐標可以表示為：

1. 若兩隻豬都死了：
（第一隻豬死前喝的那一列，第二隻豬死前喝的那一排）。

2. 只死了一隻：
1) 第一隻豬死了：（第一隻豬死前喝的那一列，五）
2) 第二隻豬死了：（5，第二隻豬死前喝的那一排）

3. 都沒死：
（5，五）

所以，對於三隻豬、125桶水：可以用（排，列，層）表示；對於四隻豬、625桶水，可以用（排，列，層，第四個空間維度的表示法）表示。

當然並不一定要把水桶排成四維的，只要正確地給它們編上號就行了。

因此，經過簡單類推，對於每隻豬能喝五排/五列的情況，能確定是否有毒的水桶數應當是：
5的n次方，其中n=豬的個數。

又因為5的4次方625小於1000，5的5次方3125大於1000，因此需要5隻豬。

---------------更新於2017兒童節-------------

評論區有人似乎不太懂如何類推到五維。其實很簡單，只需要掌握一些技巧：

1. 二維情況一隻豬一次喝5桶水，三維情況一隻豬一次喝25桶水。這是源於一小時結束時豬必須喝完全部（這裡的全部是極限情況，即5的豬的個數次方）的水的4/5，才能運用上述表示法找到毒水的坐標。

2. 其實，考慮到大家不知道如何排列，這裡有個不用排列的方法：

第一步，給這些豬編上從0到999的號碼。

第二步，將這些號碼轉為5進位並補齊為5位：

（這裡筆誤了，桶26應該是00100，感謝 @迪麗熱巴）

第三步，讓第一隻豬在第n個15分鐘內喝第一位是n的水，
第二隻豬在第n個15分鐘內喝第二位是n的水，
以此類推。

這樣，毒水的五進位編號就可以表示為：

abcde

其中

a=第一隻豬死的時間除以15，
b=第二隻豬死的時間除以15，

c=第三隻豬死的時間除以15，

d=第四隻豬死的時間除以15，

e=第五隻豬死的時間除以15。

若有豬沒死，則毒水五進位編碼對應位是0。

--------------簡陋的分割線--------------

贊數居然破兩百了，知乎小透明瑟瑟發抖

@Sun AO 的結果可以用決策樹證明，一個合法的實驗方案一共有四層，每層的分支都可以用當前豬的死活唯一表示，無論豬有沒有做實驗，都用N個0（活）或1（死）表示，且如果父親節點中對應位置為1，則位元組點中對應位置一定為1。從根節點向下每個分支合在一起唯一確定一個葉子節點，它是4*n的0-1矩陣，每一列只有5種可能，因此最多有5^n個葉子結點，也就能區分這麼多種情況。再用5進位的方法證明可行性。
不過如果毒發時間有規律，比如固定是15分鐘整發作，可以每3.6秒灌一桶，然後判斷死亡時間，這樣一桶就夠了……如果有一定範圍的分布，也可以用類似的方法增加決策樹層數，這樣就可以用更少的豬

我覺得一頭豬就夠了啊……

15分鐘就是900秒，那麼我們把1000桶水編號0~999，從第0秒開始，每0.9秒給豬喝一桶……

這樣在15分鐘內豬就喝完了1000桶水，可知接下來的15分鐘豬一定會死，只要測量死亡時間，再減去15分鐘，除以0.9，就知道毒水桶的編號了額……

所以那些說5頭的，是我理解題目有問題嗎？評論區歡迎指點

好吧果然是我理解題目有問題……

天哪，別再給我點贊了。一個搞錯了的答案竟然獲得這麼多贊，而且和大佬們的答案如此靠近，讓我惶恐不安呀！

不敢高聲語，恐驚樓上人~

位運算狀壓dp？

質譜可以么

我能答出最少犧牲豬的數目方法。一千頭每頭喝一通，哪只死哪桶有毒。

拋塊破磚。
我很好奇，如果這是一個經濟學問題，而非數學問題，或者說是一個另一類的數學問題，應該怎麼答？
比如：
其它所有條件不變，修改如下：
一批桶裝水中出現毒水的概率是千分之一（或者確定只有一桶有毒）。一桶水成本價x元，售價m*x元，一隻豬價值n*x元，我還是只有一小時時間。我作為一個賣水的人，最優解是什麼？

更正！

之前的做法每一頭豬都死了…但沒有考慮到其實豬可以不用死，多一種情況0,1,2,3,4就是五種。就用五進位編號，從[00000]到[13000]，關於什麼時候喝和四進位的時候一樣，每頭豬喝一位數，0的話級第一輪喝，1第二輪，2第三輪，3第四輪，4就是不喝。最終確定哪一桶。

死最少的結果應該是[0x444]…

最終結論應該是，n桶水，喝m輪，用（m+1）進位編號。（m+1)^x&>n，x頭豬。

雖然在這道題用正確的解法↑↑↑和錯誤的解法↓↓↓都是5頭，但要是桶數多了，高下立判！！

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

原回答：

喝四輪，用四進位編號，1000桶水從[00000]到[33220]，五頭豬喝一位數。

一共喝四輪，對應0,1,2,3。第一頭第一輪喝第一位為0的（也就是一口喝下256桶的精華[0xxxx]），第二輪喝第一位為1的[1xxxx]。根據每頭豬死的時間判斷位數是多少。比如第一位喝第一輪就死了，說明第一位編號為0，如果50分鐘的時候死了，就是3。最後確定每一位數。

同理，n桶水，喝m輪，用m進位編號。m^x&>n，x頭豬。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

很湊巧我上學期一門課的作業和這個問題非常相似。既然對於1000桶水的答案已經給出，我就描述一下作業中這個類似的問題，可以看作題中問題一定程度上的普適化版本。

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

相關知識：里德-所羅門編碼/有限域/多項式（3個中懂兩個就可以）

一種可行的方案（當然不是最優）使用了大約 $b^2lceil log_2 a ceil^2$ 只豬（大約因為中間要取質數冪），介紹如下：

首先我們確定一個有限域 $mathbb F_q$ ，其中 $q=lceil b log_2 a ceil_{prime exp}$ 。不難看出： $q > b(lceil log_q a<br /> ceil - 1)$ ，於是對於每個可能的位置 $n，我們能用一個唯一的，不超過 <img src=$ 位的 $q$ 進位數表示。

例如：我們可以用不超過6位的7進位數表示任何小於 $7^6$ 的數

對於任意一個位置 $n$ ，如果 $n$ 在 $mathbb F_q$ 中的表示是 $a_ta_{t-1}...a_1a_0$ （例如:18的7進位表示為000024，那麼 $a_5=a_4...=a_2=0, a_1=2, a_0=4$ ），則在 $mathbb F_q$ 中定義多項式 $f_n(x) = a_0 + a_1x + a_2 x^2+...+a_{t}x^{t}$ 。

之後我們可以定義 $q^2$ 個測試（每個測試使用一頭豬），每個測試有唯一的標籤 $(x,y)$ ，其中 $x,y < q$ 。在這 $a$ 桶水中，第 $n$ 桶水參與測試 $(x,y)$ 當且僅當 $f_n(x)=y$ 。

於是我們可以得出結論，如果一桶水參與的所有測試中的豬均表現出中毒跡象，則我們認為該桶水有毒。很明顯這種測試方法不會漏過任意一桶有毒的水。接下來，我要說明為什麼這種方法不會把無毒的水誤認為有毒。

（為了證明矛盾）假設有一桶水無毒，但是其參與的 $q=lceil b log_2 a ceil_{prime exp}$ 個測試均體現出中毒癥狀。因為在所有水中僅有 $b$ 桶有毒，所以根據抽屜原理可知其至少與一桶有毒的水（假設位置 $m eq n$ ）共同參與了不少於 $lceil log_q a ceil$ 個測試。那麼問題來了，這說明對於至少 $lceil log_q a ceil$ 個兩兩不同的 $x in mathbb F_q$ ，有 $f_n(x) = f_m(x)$ 。然而這些 $f_n(x), f_m(x)$ 均為 $lceil log_q a ceil - 1$ 次多項式，於是任意 $lceil log_q a ceil$ 點的取值可以唯一定義此多項式，故 $m=n$ ，與假設矛盾。

引用：NUS 課程 CS3236 Introduction to Information Theory，解法思路來源於Eric Purwanto提供的的答案和「Nonrandom binary superimposed codes, 1964」

p.s. 這種方法用於解上述問題一點都不好，要用400隻豬哈哈~~~但是當a變大時候還是挺有用的

二叉樹？有一道類似的題是用老鼠測試的

哇！超級有意思的題目！不懂資訊理論，非計算機系的學生來嘗試用所有人都能看懂的語言來強答一波~
推導未出，結論先行~高票答案沒有錯誤，5頭豬就可以完成這個偉大的使命！
要完美的解答這個題目，一定要真正弄清楚藏在題目背後的真正目的。這個目的，說的通俗易懂一些，就是我們要在有一定限制的情況下，花最少的豬力去嘗試最多的可能性。
順著這個目的，咱們來體驗一下庖丁是如何解題的~(誒好像哪裡有什麼不對勁的地方)
由淺入深，咱們先從一頭豬的故事說起。
我們假設這裡有一頭可憐的豬，旁邊的實驗台上放著一瓶題目同款毒水，用膠頭滴管取少量毒水滴入豬嘴中(做實驗要節約試劑！)，我們建立一個時間軸，並且假設此時為t=0(單位為分，下同，但均省略)，那麼，根據毒水的功效，豬死亡的概率密度函數符合區間[0，15]上的均勻分布。
等下！雖然有點兒跑偏了，但是這個信息是非常重要的！豬可能在區間[0，15]中的任何一點死去！
那假如我們做實驗的這瓶水是否有毒是未知的，為了保證實驗的準確性，如果我們在t=0時刻給豬餵了水，那麼在(0,15)這個區間內就不應再給豬喂水了。原因是這樣，假設我們在t=1的時候又換了一瓶水喂，結果豬在t=2的時候掛掉了，我們又如何判定到底是哪瓶水有毒呢？
這樣我們就看到，假如這是一個限時1小時的任務，那麼只有1頭豬的情況下，我們只能準確無誤地判定4桶水是否有毒。
好啦，到現在為止一頭豬的那些事兒已經被我們徹底搞清楚了，但是人生經驗告訴我們，雖然從無到有很不容易，但是從1到2也一樣不容易。
為了描述的方便，咱們不妨給剛才那根時間軸取個名字，就叫p1算了吧(pig 1嗎！)，如果每次喝水算1個黑點，那麼我們只能在這根軸上點出4個黑點。
現在有請我們的pig 2隆重登場。
我們自然會想，1隻豬4桶，2隻豬不過也就是8桶嗎！5隻豬怎麼可能試得完！至少不得250隻嗎?
Really?
到底該如何最大化2隻豬所能做的事情?
我們知道pig 2顯然和pig 1是獨立的，我們對pig 1做的壞事情並不會影響pig 2的死活，當然題目也排除了pig 2不小心喝到pig 1撒出的尿的這種可能性，那麼p2完全可以成為另一個不受p1影響的時間軸，原本的一維直線在這裡就可以擴展為一個二維平面，而按照上面的要求，在這個平面中我們理應可以得到4×4=16個點，也就是說，兩頭豬已經可以嘗試16種可能性了。
等等好像有點感覺讓人不能理解啊？！
咱們這麼來看。
我們可以在草稿紙上寫下一個4×4的矩陣，第一行從左到右依次編號1，2，3，4；第二行5，6，7，8，依次類推。我們把第一行代表的水在t=0時同時給pig 1喂下，把第一列代表的水同時給pig 2喂下。第二行代表的水在t=15時給pig 1喂下，第二列代表的水在t=15時給pig 2喂下。依次類推。
於是，我們就可以通過觀察2頭豬的死亡時間來獲得2根時間軸上對應的坐標值，從而唯一確定到底哪個點是有毒的。
至於高維空間的情況，把二維的情況一推廣，相信大家也全都明白了吧。
那現在問題就轉化成為了，4的多少次方剛好能超過1000?
答案當然是5咯。

如果這道題有1024桶水，那麼5頭豬會無一例外全部死亡。
而採用250頭豬，雖然是麻煩了一點，但是只會死一頭豬。
你看這個故事告訴我們，集體的力量是強大的，一個集體能做的事情會以指數形式增長。
你看這個故事又告訴我們，這世界上總有那麼些東西是不可兼得的。
那5頭豬也表示我是真的還想再活500年。

注:
該題目的意思是要找到保證一定可以找出來那瓶毒水而所採用的方法，不是說我rp爆炸第一次試就試到了然後就說最少只用1頭就可以了。。。

更新：應該是6頭。分發上把1000桶水分7份，其中6份給這6頭豬喝，如果有豬死了就是它喝的那組水裡有問題，如果都活著那就是剩下那組沒喝的有問題。重複這個過程，能把最小頭數改進成6。

更新：7應該不是最少的

7頭（其中最多死4頭），我能想到的最少。具體方法如下：
首先把1000桶水分成7份，每份143桶（有一份是142，但這不重要，以下忽略這個取整問題），給這7頭豬喝（每桶一口）。
15分鐘以後，有一頭死了，再把它喝過的143桶分成6份，每份24桶，給還活著的那6頭豬喝。
又過了15分鐘，又死了一頭豬，再把它喝過的24桶分成5份，每份5桶，分給剩下的5頭豬喝。
又過了15分鐘，又死了一頭，再把它喝過的5桶中的四桶分給剩下的4頭豬喝。
過了15分鐘，如果這4頭裡有豬死了，那麼它最後喝的那桶就是有毒的，如果都沒死，那麼5桶中沒喝的那桶就是有毒的。

同樣的推理，對於6頭豬就是不夠的。

我提供一種用組合學的思路的解法:

首先有15分鐘毒發，我們有1個小時間，所以我們可以做4輪實驗。把這個問題轉化成，有n頭豬，然後有r輪實驗的機會，可以分辨出多少桶水？

一輪實驗的時候，問題很簡單，就是2^n桶，因為根據最簡單的組合學，n維的binary vector有2^n種可能性。用3頭豬舉例，我們有8個不同的3維binary vector，然後讓每個vector對應一個桶: 0 0 0對應0號桶，表示這桶水沒有一頭豬喝，0 0 1對應1號桶，表示1號桶只有3號豬喝了.......1 0 1對應5號桶，表示5號桶被1和3兩頭豬喝了......1 1 1對應8號桶，表示三頭豬全喝了8號桶。那麼這樣子的話，稍微想一想就可以知道，喝完之後不管3頭豬死活情況如何(事實上三隻豬的死活情況也是一個3維binary vector，可以一一對應)，都可以確定唯一一桶有毒的水。

那麼可以做多輪實驗的情況呢？很好理解，先看兩輪的情況，那就是把水分成不同的組，用第一輪實驗確定哪個組有毒，第二輪再確定那個組裡哪桶有毒。同樣用3頭豬舉例，第一輪我們可以確定8個組，第二輪就可以確定桶，但是注意，不是每個組都可以有8桶水，因為第一輪有豬死了的話第二輪就不能確定8桶水了，所以應該這樣:所有豬都不喝的那一組水包含8桶，只有一隻豬喝的組(有3組)包含4桶，其中兩隻豬喝的組(也是有3組)包含2桶，所有豬都喝的那組水只能有一桶(因為萬一有毒，所有豬都掛了，第二輪也不用做了)。那麼這樣算，總共可以確定1*8 + 3*4 + 3*2 + 1*1=27桶。

觀察一下，1 3 3 1就是binomial coefficient, 表示從3頭豬裡面選0 1 2 3頭的可能性。8 4 2 1是2^i，i=0,1,2,3.

接下來這個規律應該已經很好找了，簡單的遞歸，假如有r輪的話，就把上面那個2^i換成r^i就可以了。這樣的話這個問題就解決了:這裡r=4,要讓結果&>=1000，求n是多少？

當然啦，看了別人的答案，被這個兩秒喝一桶水，然後看豬什麼時候死的答案折服了，這才是真の人才

如果用漢明碼的思路來做，豬做檢測位（聽上去好慘）

需要10隻豬

豬們分別用2的冪次標號：1，2，4，8，16，32，64，128，256，512

剩下的標號用來標記水桶：3，5，6，7，9...

每隻豬喝和自己的標號做bitwise and操作不為0的桶的水

把死了的豬的編號拿出來，做一個bitwise or

這個數字就是有毒的水的編號

想了想發現不對，豬喝水需要時間，不考慮喝水的時間的話，第一隻豬需要喝500桶水，不毒死也撐死了，不對。

不過我這個方法的好處就是只需要15分鐘就能檢測出來，好吧還是跑題了。

我就想知道兩桶毒水的那道題為什麼會被查水表

白費了我的回答，還沒存稿，哭。。。

看到評論後補充一下唄，一個是如果豬死於第n個時間段那後面的水就不用喝了，還有豬有可能不用全滅--前面三個時間段不死就能確定是最後一個了所以按理來說所有某個坐標是4的水，對應的豬都不用喝

不過高贊答案表述是比我好，直接用進位就行

-------分割線-----以下為原答案

可以只用5頭

每頭豬可以在第0,15,30,45分鐘時喝一桶水，也就是可以喝四桶水並確定哪一桶殺了它

這樣的話，考慮放入5維空間處理，每桶水編號 $(x_1,x_2,x_3,x_4,x_5)$ ，其中 $x_i$ 可取1,2,3,4. $4^5=1024$ ,編號是夠的.然後讓豬們對著編號喝就行了，比如一桶酒的編號是 $(1,2,3,3,2)$ 則第一頭豬在第0分鐘喝，第二頭在15分鐘喝，第三頭在30分鐘喝blablabla. 然後看豬們分別在什麼時候死的就知道哪桶水有毒了

就是心疼這群全滅的豬了

這不清真。

程序員/計算機學生思維:
一個1000bit的數據，有一位出錯了，需要至少幾位檢驗碼，能矯正一位差錯？

關鍵字:海明編碼

分析:二進位下2^10＞1000+10+1，10頭
五進位下5^5＞1000+5+1，5頭
十進位下10^4＞1000+4+1，4頭
11進位下11^3＞1000+3+1，3頭
40進位下40^2＞1000+2+1，2頭
知乎大部分給的5頭，
為什麼不能是4/3/2呢，時間不夠。
舉例，如果4頭，底數是10，就需要10-1=9輪15分鐘。
最佳是5頭，充分利用了時間，又沒有用很多豬。
如果想省時間，就用10頭豬，只需要15分鐘。