1000 Bottles of Wine and 10 Prisoners (Binary Representation)

Scenario

A royal cellar contains 1000 bottles of wine. Exactly one bottle is poisoned with a lethal, tasteless toxin. Any person who consumes even a microscopic drop of the poisoned wine dies after exactly 24 hours. You have 24 hours to identify the poisoned bottle using the minimum number of prisoners.

Your Task

1. Using information theory, prove why $\lceil \log_2 1000 \rceil = 10$ prisoners are strictly necessary and sufficient.
2. Describe the binary bitmask drinking assignment protocol.
3. Formulate the decoding function that maps the pattern of living and deceased prisoners at $t = 24\text{ hours}$ to the unique index of the poisoned bottle.

Constraints

• Exactly one round of drinking; 24-hour deadline.

Examples Bottle 742 in binary is $1011100110_2$. Prisoners corresponding to the 1-bits drink from this bottle.