This puzzle is taken directly from a site and reworded. The site can be found at the bottom of this question.
You are king of an empire and you are going to have a party soon. The party is the most important party you've ever hosted. You've got 1000 bottles of wine you were planning to use for the party, but you found out that one of them was poisoned.
The poison shows no effects until death. Death occurs within ten to twenty hours after drinking even the smallest amount of poison.
You have thousands of slaves at your disposal and just under 24 hours to determine which bottle has been poisoned.
You have a few prisoners soon to be executed, and it would ruin your celebration to have anyone else killed.
What is the least number of prisoners you must have to drink from the bottles to be confident that you found the poisoned wine in 24 hours?
No googling!
The site this was taken from was:
http://www.folj.com/puzzles/very-difficult-analytical-puzzles.htm
Answer
10.
Since you know that only one bottle is poisoned, you can solve this using binary logic. First, you assign every prisoner a number, from 0 to 9. Then, you give every bottle a number, from 0 to 999. If you take the binary representation of the bottle numbers, you get:
00 0000 0000
00 0000 0001
00 0000 0010
...
11 1110 0111
Every prisoner is assigned the bit corresponding to their number for each bottle. So prisoner 1 gets the $2^0$ bit, prisoner 2 gets the $2^1$ bit, prisoner 10 gets the most significant bit ($2^9$). The slaves the take a bottle each, and feed a drop to every prisoner that has a 1-bit for the bottle number. So p0 would drink from bottle 1, 3, 5, ... 999; while p9 would drink from bottle 512 and every higher bottle. Nobody drinks from bottle 0.
Prisoners drink from about 500 bottles each (a bit less for p9), which, with the help of 1000 slaves, should be possible in under 4 hours. That leaves enough time to see who dies. 500 drops is about 25 ml of wine (very rough guess) which doesn't even leave the prisoners inebriated.
If/when prisoners die, it should be easy to see which bottle is poisoned. There will be exactly one bottle that every prisoner that died, but no living prisoner, drank from. It can be found by placing a 1 for every dead prisoner and a 0 for every living one in their assigned bit order. (So if 9, 4, 3 and 1 die, bottle 10 0001 1010 is poisoned. If nobody dies, 0 is poisoned.)
Of course, if two bottles are poisoned, or one slave forgets to feed a prisoner or feeds one too many, by accident or because he's tired of your rule, you're done for.
(Note: the "nobody drinks from 0" rule is not necessary, since we have some unused binary numbers in the 0-1023 range, but I don't like senseless killing.)
No comments:
Post a Comment