Solution to Find the poisoned cask of wine
among 1000 casks
This post was contributed by Jingu Chong, who is one of our sponsors.
A nobleman is throwing a party in 24 hours, and he wants to serve wine from 1000 casks in his cellar. Unfortunately, an assassin has poisoned one of these casks. The poison takes 23 hours to take effect, and it shows no symptoms before causing death. The nobleman has servants who are “willing” to taste the bottles.
What is the least number of servants the nobleman needs to correctly identify the poisoned bottle, and what is his strategy?
Solution:
The nobleman needs 10 servants. He numbers each servant 0-9, and these represent the respective powers of 2. He numbers each bottle 1-1000. He then labels each bottle by converting the decimal number on each bottle to binary. For example, Bottle 7 becomes 0000000111 and bottle 762 becomes 1011111010. The servants drink from each bottle which has a 1 in the location of their number. So, servants 0, 1, and 2 all drink from Bottle 7 and servants 1,3,4,5,6,7, and 9 all drink from bottle number 762. The servants do this until every bottle has been tested by the appropriate servants.
The nobleman can then look at which servants died. If, for example, Servants 0, 3, 6, and 8 died, the nobleman knows that the poisoned bottle is Bottle 329 (1 + 8 + 64 + 256).