10隻老鼠和1000個瓶子，其中一瓶有毒藥
現在有10隻老鼠和1000個瓶子，其中一瓶有毒藥，另外999瓶裡面是普通的水。從外觀上分辨不出水和毒藥。喝下毒藥的生物會在一星期之後死亡，你如何利用手上的老鼠，在一星期之後，正確回答那個瓶子裡面裝的是毒藥？
這是我在面試的時候，被實際問到的問題，當下因為第一個想法是想用binary search來做，但用binary search的話，需要多次實驗，沒辦法在一星期之後立刻得到結果，所以在沒得到進一步提示的情況下，就卡住了。
上網找了一下，似乎也是一道經典題了。我們先把問題簡化一下，假設現在是3隻老鼠和8個瓶子，其中一瓶有毒藥，要如何在一星期後找出來呢？
因為我們現在手上有3隻老鼠，假設編號為A,B,C，然後我們用1代表老鼠死亡，用0代表老鼠存活，在一星期之後全部老鼠的存活情形如下：
| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 1 | 1 | 1 |
也就是說，老鼠的死活情形，剛好有8種 (2^3)，所以我們可以試著把這8種情形對應到8個瓶子上，假如三隻老鼠都活著，那就是第一個瓶子有毒藥，假如三隻都死了，那就是第八個瓶子有毒藥，以此類推。
從這個表，由上往下，就是3隻老鼠個別需要喝的瓶子，A老鼠需要喝第5,6,7,8號瓶子，B老鼠需要喝3,4,7,8號瓶子，C老鼠則需要喝2,4,6,8號瓶子。
這是3隻老鼠的情形，瞭解之後，要推廣到10隻老鼠的情形也很容易了！