毒酒迷題：現有 1024 瓶美酒，其中 2 瓶有毒。毒藥 24 小時內發作，現有 65 名死囚，怎樣能在 24 小時 01 分內找出 2 瓶毒酒？

12-05

A.一個人喝下毒酒，毒藥的發作時機是隨機的，發作時間（X）均勻分布在1分鐘到24小時整這個區間。 X～U（1, 1440）單位 min.
B.任意兩個或者以上的人喝下毒酒，他們之間（X, Y）的毒藥發作時機完全獨立的。這種獨立性不受任何外界因素影響。X,Y獨立同分布。

我想到一種解法。也用了64個死囚，還有一個打醬油了。
按照@范子逸的做法將1024瓶毒酒排成32*32的方陣，並選出64個死囚，每個死囚對應一個行或者列。在喝法上略有不同，每一行的死囚將喝掉該行以及從該行第一瓶酒起四十五度往右上斜行的酒的樣品混合物；而每一列的死囚將喝掉該列以及從該列起第一瓶酒起四十五度往左下斜行的酒的樣品混合物。（沒有圖片說得有點繞口，意思應該是明白的。）
然後判斷方法如下：最壞的情況莫過於行中有四個人死亡，列中有四個人死亡（少於八個人死亡的情況更容易判斷，不再詳說。）為了方便起見，可以在紙上畫一個正方形來輔助思考。在該種情況下，先找到可以用右斜上四十五度線相連的死囚，應該有兩條斜線滿足。斜線對應的行列做好標記。這樣行，列中分別有兩個沒有標記的死囚，對應的行列畫上直線，會有四個十字線。其中有兩個十字交點會落在斜線上，其對應的酒即要找的毒酒。

PS把這個題目和同學分享後，還有人提供了一個思路，按32*32排列一個方陣，行列編自然數序號，然後以其相鄰的兩個直邊做鏡像，然後其鏡像序號重排,重排的方法是前16個為原排列的奇數按升序排列，後16個為原排列的偶數按升序排列。這樣得到一個三個正方形組成的陣型（為3/4個64*64方陣）。然後選出64個死囚，分別對應前32行或32列，喝下對應行列的毒酒。最壞的情況也是8個人死亡。有毒酒對應行列的序號對應的奇偶數行列同樣有死囚被毒死。驗證（最笨方法一一驗證64個點）可能的點後只有毒酒點才滿足這一條件。這個辦法沒有深思，好像也可以。

PPS知乎沒辦法發圖，有時候表達清楚比較圖像化的東西呢。

這個問題有太多類似了。知乎上也有一個：http://www.zhihu.com/question/19676641
另外百度欺詐遊戲吧有更多討論：http://tieba.baidu.com/p/1015082234
————————————————————————————————————————————
基本概念就是依靠生與死/喝與不喝代表二進位中的0與1，然後得出編號
此題的難點在於兩瓶毒酒而不是一瓶，因此需要對傳統的二進位編號進行改進

以下摘自百度欺詐遊戲吧 @毒酒滴凍鴨的回答；該帖內還有不少新奇的演算法
同時還推薦 人工智慧編程吧
————————————————————————————————————————————
首先，把1024瓶酒分別編號，從0到1023，然後把每個編號的二進位值列出。例如555號，它的二進位值是：

1000101011

這裡有10個位元，分別用ABCDEFGHIJ來表示。那麼對555號來說，它的AEGIJ位元都是1，BCDFH位元都是0。

接下來為65位死囚分成三組：

棒組10人，分別代號為棒A、棒B、棒C、棒D、棒E、棒F、棒G、棒H、棒I、棒J。
洞組10人，分別代號為洞A、洞B、洞C、洞D、洞E、洞F、洞G、洞H、洞I、洞J。
異組45人，分別代號為AB、AC、AD、AE、AF、AG、AH、AI、AJ；BC、BD、BE、BF、BG、BH、BI、BJ；CD、CE、CF、CG、CH、CI、CJ；DE、DF、DG、DH、DI、DJ；EF、EG、EH、EI、EJ；FG、FH、FI、FJ；GH、GI、GJ；HI、HJ；IJ。

那麼如何分配毒酒呢？我們根據每一個編號的二進位值來決定：

如果k位元（k可以是ABCDEFGHIJ的其中之一）是1，那麼棒組的棒k就要試飲該瓶毒酒，洞組的洞k不用試；如果k位元是0，那麼棒k不用試，洞k要試。

另外，對於任何兩位元組合m,n（ABCDEFGHIJ裡面的其中之二），假如m和n的位元值不相等（一個是1、一個是0），那麼異組的mn就要試飲該瓶毒酒；否則若兩位元值相等（彼此都是1或彼此都是0），mn就不用試。

就以上面的555號作一個例子，棒組的棒A、棒E、棒G、棒I、棒J五人要試飲該瓶毒酒，另外五人不用試；洞組的洞B、洞C、洞D、洞F、洞H五人要試飲該瓶毒酒，另外五人不用試。

最後，異組的AB、AC、AD、AF、AH、BE、CE、DE、EF、EH、BG、CG、DG、FG、GH、BI、CI、DI、FI、HI、BJ、CJ、DJ、FJ、HJ共5*5=25人要試飲該瓶毒酒，另外20人不用試。

（只要把等於1的位元組和等於0的位元組兩兩配對，就能得出所有異組要試飲該瓶毒酒的成員名單。）

按此規則，0到1023號的每瓶酒都能很快定出有哪些死囚要試飲，哪些不用試。必須在15分鐘內分配混合好每人所需負責的毒酒樣本，並全部完成試飲程序。

（容易算出所有死囚每人要分別負責512瓶酒的試飲，但是在完善而有條理的安排和適當的工具協助下，15分鐘內完成是絕對有可能的……）

好了，經過24小時15分鐘的觀察時間後，有些人暴斃了。怎樣決定哪兩瓶才是毒酒呢？先把兩瓶毒酒代號為甲和乙，它們的二進位值如下代表：

甲A 甲B 甲C 甲D 甲E 甲F 甲G 甲H 甲I 甲J
乙A 乙B 乙C 乙D 乙E 乙F 乙G 乙H 乙I 乙J

只要把這20個位元值全部解出來，就能直接知道兩瓶毒酒的編號了……但應該怎樣解呢？

我們先看棒組和洞組的死亡情況：假如棒k死了而洞k沒有死，那麼兩瓶毒酒編號的k位元肯定都不是0，所以甲k和乙k的位元值一定同時是1；相反棒k沒有死而洞k死了，那麼兩瓶毒酒編號的k位元肯定都不是1，所以甲k和乙k的位元值一定同時是0。

當然，還有一個情況，就是棒k和洞k兩人都死了……這代表了兩瓶毒酒的k位元一個是1，一個是0。但是這裡有兩種可能：甲k=1、乙k=0或甲k=0、乙k=1……怎麼決定呢？這時就要靠異組的45人了：

首先，假設最左邊出現棒洞兩人同死的是m位元……那麼我們直接設定甲m=0、乙m=1。

（這裡我們是在規定甲的編號一定比乙小，因為m位元左邊的全部位元值都是相同的，所以m位元決定了甲乙的大小排序。）

再來假設m位元右邊的n位元是另一個出現棒洞兩人同死的位元，那麼有兩種可能：甲n=1、乙n=0或甲n=0、乙n=1……這時我們看看異組的mn是生是死：

如果mn沒有事，那麼(甲m,甲n)和(乙m,乙n)肯定都是相同的，所以甲n=0、乙n=1。

如果mn暴斃了，那麼(甲m,甲n)和(乙m,乙n)肯定都是不同的，所以甲n=1、乙n=0。

根據這些規則，很容易就可以解出甲和乙全部的20個位元值，然後把二進位換算成十進位就能找到兩瓶毒酒的編號了。

一個極端的例子，假如棒組和洞組的20人全部暴斃，而異組的45人卻一個都沒有死，那麼毒酒是哪兩瓶呢？很簡單，就是編號0(0000000000)和1023(1111111111)的兩瓶。

註：此方法並不是最優解，帖子內還有其他所需人數更少的解

沒想到知乎里也有常上數學研髮網的朋友。可以看看這篇論文：
http://www.combinatorics.org/Volume_5/PDF/v5i1r39.pdf
——————————補充分割線——————————
老帖子又被頂起來，才發現我提供的pdf鏈接已經失效了，不過就算論文能夠下載，也不容易看懂(我就沒怎麼看懂)，論文中只給出了上界和下界，沒有給具體構造方案，所以我再說一下構造的方法，實際上用不了65個人，論文中給出的界限大概31-33人就可以，我提供一個構造方案，大概只需要40人，也是前兩年看到過的一個方法，並非原創。

設f(n)表示n瓶酒中有1或2瓶毒酒的情況下，測試需要的囚犯數目。
對於一個n*n的方陣，如果知道n行中那些是毒酒，n列中哪些是毒酒，便可將毒酒範圍縮小至1、2、4瓶。如果範圍是1或2瓶，則可以直接推出這1或2瓶有毒，如果範圍是4瓶，則存在兩種情況，分別對應矩形的兩條對角線，如果採用一種方式對頂點進行編號，使方陣中的任意矩形2條對角線的編號不完全一樣，那麼便可以區分是那條對角線上的酒有毒，事實上只需要n/2種編號，就可以實現任意矩形的對角線對應的頂點編號不完全一樣。以n = 6為例

012321
101232
210123
321012
232101
123210

(每行向右移1位，其中編號為0的不用喝)

在這裡，並不是需要n人去試每一行或列是否有毒，而是把問題轉化了，一個n*n的問題，轉化為了3個Sqrt級的子問題，f(n^2) &<= f(n) + f(n) + f(n/2) 其中前2個f(n)是用判斷行列的，f(n/2)是用來判斷對角線編號的。

有了上面這個遞推式，可以寫一個loglog(n)的動態規劃，來求解。
簡單寫了一個C#程序。

using System;

namespace Zhihu
{
class Program
{
static int[] Counter;

static void Main(string[] args)
{
int count = 1024;
Counter = new int[count + 1];
Console.WriteLine("需要:{0}人", F(count));
Console.ReadKey();
}

static int F(int n)
{
if (n &<= 0)
return 0;
else if (n &<= 4)
return n;

if (Counter[n] == 0)
{
int k = (int)Math.Sqrt(n - 1) + 1;
if (k * k - k &>= n)
Counter[n] = F(k) + F(k - 1) + F(k / 2);
else
Counter[n] = 2 * F(k) + F(k / 2);
}

return Counter[n];
}
}
}

n = 1024時，這個構造方法需要40人。
當然還有更好的方法，大家可以看看數學研髮網的帖子（幫大家找了一下以前的帖子）。
http://bbs.emath.ac.cn/thread-1511-1-1.html
我說的方法來自tannis_jin，mathe在帖子裡面給出了32人的解以及求解程序。

感謝這麼多人贊同，但是我的答案是錯誤的。
假設兩瓶毒酒的坐標是（x1,y1), (x2,y2),
4個囚犯死亡實際上有4瓶酒可能有毒（x1, y1) (x1, y2), (x2, y1), (x2, y2)
所以辦法確定具體有毒的是哪兩瓶。
不過以浪費2瓶酒的代價換來的是大部分死囚的存活，還是很人道的哈。
----------以下是原答案----------
將1024瓶毒酒排成32*32的方陣。
選出64個死囚，每個死囚對應一個行或者列。
每個死囚將自己所對應的行或者列的32瓶酒混合後喝下。
24小時後會有不超過4個死囚被毒死。
找出他們對應行和列，交叉點上的就是有毒的酒。

瀉藥~

感謝@范子逸的提示，我的一般性解法：

酒數目：

人數：先除去一個最後收屍的，剩下64個人，分2組，每組人數：

分酒試喝：

將1024瓶酒，分為32*32組；
把死囚分為32+32個；
每個人試著一口氣喝下分給自己的那全部32瓶酒，而不喝其他人的酒（必須按照要求喝）；

分析：按照下表（樣例），將24小時內死掉的人所在的行和列畫出來，交叉點畫圈圈，就是毒酒的位置。

有兩種可能：
1. （最多）4個人死掉：兩瓶毒藥不同行、不同列。
2. 3個人死掉：兩瓶毒藥在同一行、或同一列。
最後可以根據畫出的行和列的交叉位置（圓圈位置），判斷出哪瓶酒是毒藥（有點太驚心動魄又殘忍了吧）。

更一般地，

假設：
1. 總人數：p；
2. 總瓶數：N；
3. 毒藥瓶數：n。

方法：「構造n次元空間」
1. 將N瓶酒均分為n組，每組瓶數為：

即：

其中，a、m均為自然數。
2. 將（p-b）個人均分為n組，每組人數為：

即：

其中：b為自然數（收屍者），且b&3. 使用之前的方法試喝，在n次空間內畫圈圈，可找出這n瓶毒酒；
4. 死掉的人數範圍（閉區間）：

5. 緩死者（倖存者）數目：p-（上邊的實際死亡人數）討論：

為使儘可能少的人冒「立即死亡」的危險，可以盡量使a、m接近；
也可以適當增加n，但會增加死亡人數；
「最優解」條件：n=m，而a、m最接近。

例如：

按照原題數字，有64個人冒著生命危險，最多死4個；
取a=4，m=5，n=5，可以使冒險人數降低為：4*5=20人，但死亡人數增加為9~25個人。

p.s.

雖說已是「死囚」了，怎麼可以隨意剝奪別人暫存的生命？且暫不說死刑是否合理。
死囚可以選擇不喝酒嗎？
如何選出最後收屍的那個人？
如何平衡風險與必死人數？（最後的討論）

其實就是信息量的問題，因為發作時間是隨機的，所以一個人能表示是信息量只有生/死兩種，為了表示1024種狀態，需要的位元是log（2）1024=10。換個說法吧，把數量降下來，只有8桶，log（2）8=3,給人編號1,2,3,用這3個元素做排列組合，可以得到的集合是｛空,1,2,3,12,13,23,123｝在桶上寫上標上12,13,123這些，寫有牌號的就喝，最後看誰死，查牌號就好。

還有個擴展的，就是24小時後才死，那就是一個人能表示24種狀態，比如1024桶，最少人數就是log（24）1024取整

找被打開的那兩瓶？

靠，我先想到的居然是1024

我把 @覃魯和 @范子逸的答案複述一下
酒擺成32行X32列，囚犯分成2隊，一隊每人喝1橫行，一隊每人喝一豎列
然後會出現兩種可能

第1種：一列兩行 or 兩列一行。

喝第3行的死了，喝第2列和第3列的死了，由此判斷（2，3）和（3，3）是有毒的。
非常準確

第二種：兩列兩行

第3行的死了，第4行的死了，第3列的死了，第5列的死了。
那麼可以判斷ABCD四瓶可能有有毒，AD或者BC。
假設第一個死的人是3行，第二個死的人是3列，那麼65個人用了64個還剩1個，喝A點的酒。死了說明是AD，沒死就說明是BC
但是時間夠不夠就不好說了所以在這兩位的肩膀上，我想可以每瓶酒分2份，每份為：排成8*8*16層的兩堆，需要8+8+16個人，每人喝一個面。這樣每堆能測出8個點，4個點，2個點。
第一個排列和第二個排列次序不同。比如1號酒，在排列1中位置（1,1,1），在排列2中位置（4,2,15），而且不是所有的瓶子移動都是不規律的
那麼8個點中重複的2瓶酒就是有毒的

這題不是智力吧中，毒酒滴凍鴨發的文章嗎，咋到這裡來了？

有沒有這樣的問題，不知道有多少瓶有毒，怎麼確定有毒的個數和哪些有毒？

這種問題基本都是抽象為二進位數，一個單元的兩種狀態對應二進位數中每一位取0還是取1，只要指明了這個思想方向，剩下的事就比較簡單了。

10個就夠了，理論上，1024是10位的

以8瓶酒為例，先分4瓶兩組，挑出一人去喝其中一組的混合，若掛掉，則酒在該組，然後下一個就喝該組的酒，若不掛，在另一組，則喝另一組的酒，以此二分，會發現二分的樹層數是log N

類推1024瓶酒，10個犯人足夠，有效利用二分是解決此類問題的最佳答案。

ps：美國士兵檢查AIDS也是利用這個方法的