91. Finding the Poisoned Bottle
The emperor has 1 000 bottles of wine locked away for tomorrow night’s banquet. Unfortunately, a spy has slipped poison into exactly one of them. The poison is lethal but slow: anyone who drinks even a single drop will die exactly 24 hours after drinking.
The emperor has 10 condemned prisoners he can use as taste-testers. A prisoner may sip from any number of bottles. After 24 hours it will be apparent which prisoners are dead and which are alive, and this is the only information that will be available before the banquet.
Can the emperor always determine with certainty which single bottle is poisoned using at most these 10 prisoners? If so:
- Describe a tasting scheme that works.
- State the minimum number of prisoners required to guarantee success.
- Under your scheme, how many prisoners are guaranteed to die?
Added 25 September 2009
Hint: Number the bottles 1–1000 and think of writing each number in binary. Let each prisoner correspond to one binary digit.
Solution:
Minimum number of prisoners. Each prisoner has two possible outcomes (lives or dies), so n prisoners provide at most 2n distinct outcome patterns. We need at least as many patterns as bottles, so we need the smallest n for which 2n ≥ 1000. Because 29 = 512 < 1000 and 210 = 1024 ≥ 1000, the minimum is 10 prisoners.
Labelling scheme.
- Label the bottles 1–1000.
- Write each label as a 10-bit binary number (1 = 0000000001, 1000 = 1111101000).
- Assign each of the 10 prisoners to one bit position: prisoner 1 to the least-significant bit (20), prisoner 2 to the next (21), …, prisoner 10 to the most-significant bit (29).
- For every bottle, let each prisoner whose assigned bit is 1 in that bottle’s binary label take a sip from that bottle.
Reading the result. After 24 hours, record which prisoners died. Treat their numbers as the 1-bits of a 10-bit binary number; the resulting binary value is exactly the label of the poisoned bottle.
Casualties. In the worst case all 10 prisoners could have tasted the poisoned bottle, so up to 10 may die. No scheme using only outcome patterns (live/die) can guarantee fewer deaths while still uniquely identifying one of 1000 bottles in a single 24-hour round.
Thus the emperor can infallibly find the poisoned bottle with exactly 10 prisoners, and the number of prisoners who die is between 0 and 10 inclusive, with 10 being the guaranteed upper bound.
Comments (0)
No comments yet. Be the first!
Add a Comment or Suggest an Answer