A king has 1000 bottles of wine, and one of them is poisoned. The poison is so potent that even just a sip of it would be fatal. However, the poison takes effect exactly 30 days after consumption.The king has 10 prisoners at his disposal to find out which bottle is poisoned. He decides to use them in a test to find the poisoned bottle.
The king is very intelligent and has a perfect memory, and the prisoners are all willing to participate in this deadly game for their freedom.
How can the king use the prisoners to find out which bottle is poisoned in just one round of testing, ensuring the fewest possible casualties?
Show Answer
- Label the Bottles: Label each of the 1000 bottles with a unique number from 1 to 1000.
- Binary Representation: Convert each bottle number into a binary representation. Since 1000 in binary is ‘1111101000’, you will need 10 binary digits (or bits) to represent each number. For example, bottle number 13 would be represented as ‘0000001101’.
- Assign Prisoners to Bits: Assign each of the 10 prisoners to one of the 10 binary digit positions.
- Administer the Wine: For each bottle, if the binary representation of its number has a ‘1’ in the position assigned to a prisoner, that prisoner takes a sip from the bottle. If it’s a ‘0’, the prisoner does not take a sip from that bottle.
- For example, for bottle number 13 (‘0000001101’), prisoners assigned to positions 4 and 2 would take a sip, since those are the positions of the ‘1’s in the binary representation.
- Wait 30 Days: After 30 days, observe which prisoners have died.
- Determine the Poisoned Bottle: Look at the binary positions assigned to each dead prisoner. If a prisoner is dead, that means there was a ‘1’ in that binary position for the poisoned bottle’s number. If a prisoner is alive, there was a ‘0’ in that binary position.
- By noting which prisoners died, you can reconstruct the binary representation of the poisoned bottle’s number, and thus identify the poisoned bottle.
