51. How Many Tasters to Find the Poisoned Cask? A king keeps 1000 different casks of wine in his cellar. Yesterday a spy managed to pour a slow-acting poison into exactly one of the casks before being caught. The poison has two special properties: One drop is enough to kill. The victim always dies precisely 30 days after drinking it. The king’s anniversary banquet is in 30 days, and he wants to serve only the safe wine. He may use prisoners as tasters today (the only day he has access to them) and observe who is still alive on the banquet day. What is the minimum number of prisoners the king must use to be certain of identifying the poisoned cask among the 1000? If the king has only 10 prisoners available, what is the largest number of casks for which he could still guarantee finding the single poisoned one in 30 days? Added 6 October 2008 Show Hint Show Solution Hint: Think of each prisoner as reporting a single binary digit (alive = 0, dead = 1). How many different patterns of deaths can you create with n prisoners? Solution: 1. Label the casks from 1 to 1000 and write each label in binary. Give each prisoner a sip from every cask whose binary representation has a 1 in the position assigned to that prisoner. After 30 days, the pattern of survivors forms the binary number of the poisoned cask. You need enough prisoners that their death/survival pattern can distinguish among 1000 possibilities. With p prisoners you have 2p possible patterns. The smallest p with 2p ≥ 1000 is 10 (because 29=512 < 1000 < 210=1024). So the minimum is 10 prisoners. 2. With 10 prisoners you get at most 210=1024 different patterns. One of these patterns is “no one dies,” which cannot happen because we know exactly one cask is poisoned. Therefore the scheme can uniquely identify the poison among at most 1024−1 = 1023 casks.
Comments (0)
No comments yet. Be the first!
Add a Comment or Suggest an Answer