The Emperor's Wines
You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.
The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.
You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.
You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.
What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
Taken from: http://www.folj.com/puzzles/very-difficult-analytical-puzzles.htm
The answer is 10.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The fact that death may occur in as little as 10 hours is irrelevant to this problem, as we must explicitly plan for the worst case. So we get to distribute the bottles exactly once, and in doing so we must guarantee that we'll get the information needed to to identify the poison bottle.
If we give X prisoners wine, we can learn, at most, X bits of information - one bit for each prisoner, whether they died or not. So, we must feed wine to 1 0 prisoners at minimum, since 2 9 < 1 0 0 0 < 2 1 0 . It turns out 1 0 is all we need.
Give each wine bottle a number, from 0 to 999. Convert that number into a 10-digit binary string. For each digit that is 1, feed the corresponding prisoner a portion of that wine bottle. (One prisoner gets 2 0 , the next gets 2 1 , and so on up to 2 9 .) Do this for all of the wine bottles.
The next day, note which prisoners died, if any, and reconstruct the binary representation of the wine bottle number based on their positions. This uniquely determines the wine bottle that was poisoned.