Problem #8 HARD
The Poisoned Wine Bottles
Google Math Logic
Problem Statement
A king has 1,000 bottles of wine. An assassin poisons exactly one bottle. The poison is extremely deadly and has no taste or smell, but it takes exactly 24 hours to take effect.
The king wants to find the poisoned bottle before a royal banquet in 24 hours. He has a group of prisoners whom he can use as taste testers.
What is the minimum number of prisoners required to identify the single poisoned bottle within 24 hours?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
You need exactly 10 prisoners by labeling bottles in binary (10 bits) and having each prisoner drink from bottles where their assigned bit is 1.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
The problem can be solved using binary representation. Since 2^10 = 1024, which is greater than 1000, we can uniquely represent each bottle using a 10-digit binary number.
Here is the setup:
1. Label the 1000 bottles from 1 to 1000. Express each label as a 10-bit binary number (e.g., Bottle 1 is 0000000001, Bottle 1000 is 1111101000).
2. Label the 10 prisoners from 1 to 10, corresponding to the 10 bit positions (from least significant to most significant).
3. For each bottle, a prisoner drinks a drop of wine from it if and only if the bit at their corresponding position in the bottle's binary label is 1. For example, Prisoner 1 drinks from all odd-numbered bottles.
4. Wait 24 hours.
To find the poisoned bottle, look at which prisoners die. If Prisoner 1 and Prisoner 3 die, the poisoned bottle's binary representation has 1s in positions 1 and 3, which is 0000000101 (Bottle 5). By converting the survival pattern back to decimal, the king can pinpoint the exact bottle.