Gateways To Joy
/
Puzzles
/
Set 5
/
Poisoned Wine Barrels
Poisoned Wine Barrels
12 Sep 2008
Puzzle

An enemy spy has poisoned one out of 1000 barrels of wine in a king's cellar. Even a sip of the poisoned wine has potency to kill. However, the effects of the poison show only in 30 days. The king asks the royal jailor to identify the poisoned barrel within 30 days. What is the least number of prisoners the jailor must employ to identify the poisoned barrel?

Source
Solution

The jailor prepares 10 mixtures labeled 0, 1, 2, ..., 9. Wine from the i-th barrel is added to those mixtures that correspond to 1's in the binary representation of i. Thus it takes exactly 10 prisoners to find out the poisoned barrel.

© Copyright 2008—2017, Gurmeet Manku.
Send me email