兔子與毒酒

在 TonyQ 的 FB 看到一道題目,內容是:

有16瓶外觀一樣的酒,其中有1瓶是毒酒。兔子喝了毒酒之後,1個小時後會死亡。1個半小時之後,這些酒要拿到宴會上使用。兔子可用數量不限,請在宴會開始前,用最少隻兔子找出毒酒。

這邊很直觀的作法是,一隻兔子喝一瓶酒,總共使用16隻兔子可以找出毒酒。由於時間限制的關係,不能讓一隻兔子喝一瓶,等一個小時,若活著再繼續喝。(這邊有個解法是,讓兔子每隔1分鐘喝1瓶酒,等過了1小時之後紀錄兔子死亡時間,就可以回推是哪一瓶酒。不過這不是題目最主要的用意XD)

最好的作法是,把兔子的生死狀態視為0與1,也就是可以看成1個 bit。而16瓶酒表示16個狀態,原本的問題就可以轉換成,需要幾個 bits 去表示16個數字?答案就是需要4個 bits。把所有可能性寫出來的話就如下所示:

0001 -> 1
0010 -> 2
0011 -> 3
0100 -> 4
0101 -> 5
0110 -> 6
0111 -> 7
1000 -> 8
1001 -> 9
1010 -> 10
1011 -> 11
1100 -> 12
1101 -> 13
1110 -> 14
1111 -> 15
0000 -> 16

假設從前面數來,第1隻跟第3隻兔子死亡,就可以知道是編號10的酒是有毒的。還好只是題目,不然1隻兔子要喝8瓶酒阿XD。

Show your support

Clapping shows how much you appreciated Gary Yeh’s story.