Interview Question: Poisoned Prisoners

Challenge:

A king receives 1000 bottles of wine, 1 of which he knows to be poisoned. He does not know which bottle is poisoned so he will use ten prisoners to test the wine. The king wants this task done quickly so he can start drinking his wine as soon as possible so he hires you to find the fastest way to solve this wasting as little wine as possible. The prisoners are only allowed have wine once a day. Even the smallest amount of the poisoned wine is enough to poison and kill a prisoner.

Solution:

For this lets assume that when a prisoner drinks wine he has a insignificantly small amount.

In this case most people start by making each prisoner try 100 wine each. The naive path to take here is having each prisoner drink it one at a time taking (at worst) 100 days to find the poisoned wine. This is not bad however what if we mix 100 of the samples into one drink.

Now each prisoner tries 100 wine samples at once so when a prisoner gets poisoned we know which 100 bottles hold the poisoned bottle. We can redo this with 100 bottles and 9 prisoners each trying 11 and one trying 12. We can redo this again once we find the 12 possible poisoned bottles and have 8 prisoners 1 or 2 each. We may find the one here or we may have to go another day. This method takes at worst 4 days and at best 3. This is a lot better than our previous 100 day result.

However we can mix the wines is a smarter way. Firstly lets number each bottle from 1 to 1000. Each of these numbers have a binary representation that can be written in 10 digits. Lets number the prisoners from 1 to 10. Now we serve the wine to the nth prisoner if the nth digit in the binary representation is 1. As previously done we mix the sample together so each prisoner can drink it in one day. Now a set of prisoners will die and we can use their number to recreate the number. Example if the prisoners 3, 5, 6, 9 die then we get 308. This means that wine number 308 is poisoned. We can do this because each number has a unique binary representation which has a bijection to the set of poisoned prisoners. Thus knowing the set we can use the bijection to figure out the bottle number accurately in 1 day.