試酒問題◤排列與組合◢

他最小需要找兩個死囚。

第一個喝下一口第一支，兩分鐘後不死喝第二支，兩分鐘後不死喝第三支，⋯
直至喝第n支兩分鐘後死，那第n支酒是有毒。

第二個死囚喝下一口第(n+1)支，兩分鐘後不死喝第(n+2)支，⋯
直至喝第(n+k)支兩分鐘後死，那第(n+k)支酒是有毒。

2014-03-14 21:54:26 補充：
依你這個提示，那我知你想點計了。

答案是16個死囚。

2014-03-17 18:12:19 補充：
那些年 說得對，是 20 個，這幾天試了多個，還是覺得 20 的這個答案最易做到。
先將酒分AB兩組，每組500支，分給2個死囚，若2個都死，那每組都有一支毒酒。
用 "提示" 的方法，得知每組再用9個死囚，就可分出那支有毒，
所以總共用死囚：
2 + 9*2
= 20 (個)

若只得喝A組酒的死，則兩支都在A組那500支內。
將這500支分CD兩組，每組250支，分給2個死囚，若2個都死，那每組都有一支毒酒。
因每組都有一支毒酒，用 "提示" 的方法，得知每組再用8個死囚，就可分出那支有毒，
所以總共用死囚：
2 + 2 + 8*2
= 20 (個)

2014-03-17 18:13:24 補充：
若只得喝D組酒的死，則兩支都在D組那250支內。
將這250支分EF兩組，每組125支，分給2個死囚，若2個都死，那每組都有一支毒酒。
因每組都有一支毒酒，用 "提示" 的方法，得知每組再用7個死囚，就可分出那支有毒，
所以總共用死囚：
2 + 2 + 2 + 7*2
= 20 (個)

... 如此類推。若次次分兩組都只死一個死囚，那
500, 250, 125, 63, 32, 16, 8, 4, 2, 1
所以總共用死囚：
2 + 2 + ... + 2 (總共10次)
= 20 (個)

所以最小需要20個死囚。

29 個肯定不是最小，但 16 個也不見得行得通。
既然若只得一支有毒的話，最小需要10個死囚，
那若有二支有毒的話，就最小需要20個死囚了。

呢類既題目要逐層慢慢分析，以下係我對呢題既分折︰
首先將酒編碼先啦,1-1000
然後，我地假設試親酒既人都死哂
(咁樣先係最難決定邊支酒有毒,所以就以呢個情況為標準,以下會有解釋)
第1個人試1-500,第2個人試，知道係頭500支定尾500支有毒。
如果有1個人無死,代表2支毒酒一定係1-500 OR 501-1000
如果呢個情況下我只需要搵人試1-250,501-750 就可以 即刻搵出毒酒既位置,所以呢個會低估左死囚既次數，因此我地當每次試酒都係全部人死哂,咁樣可能性會比較多，咁就可以確保邊兩支有毒。
好,兩個人都死哂,代表有1支係1-500,有1支係501-1000(2)
然後，我地可以搵1人試1-250,501-750,1人試251-500,751-1000
假設都係兩個人死哂,我地可以有既可能係
(1)兩支酒係1-250,751-1000
(2)兩支酒係251-750
為左確定呢個情況,搵個人試251-750,如果呢個人死左代表情況(2),無死代表(1)
我地而家用左5個人。
跟住搵1個人試1-125,251-375,501-625,751-875,另1個人試其他
佢地又死哂,而家又出現左4個情況
(1)1-125,876-1000
(2)126-250,751-875
(3)251-375,626-750
(4)376-625
不過睇返之前,我地試左1-250,751-1000(1)(2)251-750(3)(4),
又假設依2個人死哂,咁我地試埋(2)(3) 就可以知係邊個情況了.
我地用左8個人。
睇多1層就可以推理到總共要幾多人。
搵個人試1-63,126-188,251-313,376-438,.....,876-938,另1人試其他
我地而家有既可能係,1000個數分左16份
(1)(16),(2)(15),(3)(14).....(8)(9) 總共有8個情況,當(1)(16)叫A....(8)(9)叫H
但我地知道(A,B)(C,D)(E,F)(G,H)=第三層的(1)(2)(3)(4) 4揀1係邊個
因此,我地試埋(ACEG) 或者(BDFH) 就可以知係ABCDEFGH 那個情況
我地可以睇到,除左第1層我地要2個人之外,其他層數都要3個人.
而1000去到1,總共有10層
(1000,500,250,125,63,32,16,8,4,2,1),我地可以推斷,
最少需要死囚2+3X9=29

2014-03-16 22:20:53 補充：
雖然我做到後面無咁肯定我試得岩唔岩
因為試得準先可以令到後面卡啦卡啦試完後只剩1次要試
但因為真係需時，所以無咁做到。

我覺得憑規律搵答案就可以了
你可以發現如果有人無死既話,試既次數會減少
如果次次試酒都有1個人唔洗死,咁即係果2支毒酒肯定連埋
如果係咁即係同1支毒酒1樣,不過反而比1支毒酒少1次
因為試到2既時候已可肯定2支皆是毒酒,不用再試
但呢個情況幾乎無可能發生,所以就試最難試既,
最後應該會係咁

2014-03-16 22:21:01 補充：
(1,1000)(2,999)(3,998)....(500,501) 500種可能,如果2個一組,我地已經會知係邊組
再試(1,3,5....,499,502,504,.....1000) 就可以搵到係邊2支酒了。

以上係考慮左最多可能情況下既最少需要死囚次數。

2014-03-16 22:24:31 補充：
唔記得講 以上個情況係理想情況, 因為某D組 去到第9層已經會停左
(1000,500,250,125,62,31,15,7,3,1),
但我地係最後面都係可以只試1次而搵到毒酒,做法同理。

2014-03-17 15:12:11 補充：
為何29個不是最小?
可不可以舉1個例子是小於29個死囚卻能試出的?

2014-03-23 09:49:29 補充：
樓上既方法係不可能正確分到的

假設你分做AB組既時候
A(1-500)B(501-1000) B死囚無死,代表酒係1-500
後你再將A既一半酒分比1個死囚(1-250), 相
信你既意思係以另1個死囚試B既一半吧(501-750),咁依個人因為肯定唔死而變得無意義
而試A一半毒酒既人,如果佢無死,你肯定2支毒酒係251-500
但如果佢死左呢?你點知毒酒係2支都係1-250,定係1支1-250,1支251-500?

2014-03-23 09:49:35 補充：
提示是指1支毒酒的情況下，現在是2支毒酒，原理不是一樣的。
睇1支毒酒既時候,我地每層得2個可能(0,1) 同(1,0)
但睇2支毒酒既時候 其實係有3個可能(0,2),(2,0), (1,1),
係第2層開始,(如果咁岩係1,1你就分到),但(0,2)既時候代表你已經唔可以用1個死囚分到

你既假設係國王有無限既時間試酒,而題目表明只可試一個回合(2小時)

2014-03-23 09:50:26 補充：
你先答2支，後答16支，然後附和別人說20支，別依賴提示吧

999 人試 999 支酒
若發現有 2 個人死，他們試的那 2 支便有毒
若發現有 1 個人死，沒有試的那 1 支便有毒