The King's Poisoned Wine

The problem
1,000 bottles · exactly one poisoned · 24 hoursminimum prisoners as tasters?

A king has 1,000 bottles of wine for tomorrow night's banquet. He just learned that exactly one is poisoned. The poison takes 24 hours to act, then kills. The banquet is in 24 hours.

The king has prisoners he can use as tasters. Each prisoner can drink from any combination of bottles. After 24 hours, prisoners who drank from the poisoned bottle die.

What's the minimum number of prisoners needed to guarantee identifying the poisoned bottle in time?

Tempting (but wrong)
500? 100? one per bottle?only one round of tasting before the banquet

People typically guess in the hundreds:

  • "500" — split the bottles in half and use one prisoner per half? But the timing only allows one round of tasting; you can't iterate.
  • "100" — split into 10 groups of 100, with one prisoner per group? Identifies the group but not the bottle within it.
  • "log⁡21000≈10\log_2 1000 \approx 10 rounds" — closer, but the question is prisoners, not rounds. You have one shot, not 10 sequential days.

The correct answer is smaller, exact, and depends on thinking about information, not iteration.