1000 bottles of wine, one poisoned

Question

A king has 1000 bottles of wine, exactly one of which is poisoned. The poison is so potent that any amount is lethal, and it acts with a delay: a prisoner who drinks poisoned wine dies exactly 24 hours later, showing no symptoms before then. The king has a supply of prisoners he can use as tasters, and he needs to find the poisoned bottle in 24 hours (so each prisoner can be given a mixture to sip only once, all at the same time). What is the minimum number of prisoners needed?

Accepted Answer

The answer is 10 prisoners. The core idea: after 24 hours, each prisoner is in one of two states, alive or dead. That is one bit of information per prisoner. With n prisoners you get n bits, able to distinguish 2^n outcomes. Since 2^{10} = 1024 \ge 1000, ten prisoners suffice, and 2^9 = 512 < 1000, so nine do not. The encoding scheme. Number the bottles 0 through 999 and write each number in binary with 10 digits. Assign prisoner i (for i = 0,\dots,9) to bit position i. - Prisoner i drinks from every bottle whose i-th binary digit is 1. All prisoners sip their assigned mixtures at the same ti…

1000 bottles of wine, one poisoned

Your answer

More Brainteasers questions