Poisoned Wine Barrels
12 Sep 2008

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?


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—2018, Gurmeet Manku.