The Poisoned Wine Bottles and Binary Encoding

You have 1,000 bottles of wine. Exactly one is poisoned. You have some number of test rats: each rat drinks from any subset of bottles you choose, and dies (eventually, all at the same known time) if and only if it drank from the poisoned bottle. You must identify the poisoned bottle using as few rats as possible, with everyone drinking simultaneously and just one round of testing. How many rats does it take? The answer is 10 — far fewer than the 1,000 a naive one-rat-per-bottle approach would suggest, and the mechanism is exactly binary encoding.

The core idea: number every bottle in binary, one rat per digit

Since $2^{10} = 1024 \ge 1000$, every bottle from 1 to 1000 can be written as a unique 10-digit binary number, using 0s and 1s. Assign rat $i$ (for $i = 1, \dots, 10$) to drink from every bottle whose binary label has a 1 in position $i$. After the tasting, look at which rats died: the pattern of dead and alive rats, read as a binary number (dead = 1, alive = 0), is the binary label of the poisoned bottle — because the poisoned bottle is the unique bottle that was drunk by exactly the rats that died, by construction.

Each rat isn't answering "did you drink the poisoned bottle" in isolation — it's answering "is there a 1 in this specific digit of the poisoned bottle's address," and 10 such yes/no answers are exactly enough to spell out any address up to 1,023.

Worked example: a small version with 8 bottles

Label bottles 1 through 8 with three-bit binary addresses (using $000$ through $111$, or equivalently 1 through 8 shifted by one): $1{=}001, 2{=}010, 3{=}011, 4{=}100, 5{=}101, 6{=}110, 7{=}111, 8{=}000$ (using $000$ for the 8th bottle, treating it as address zero). Use 3 rats since $2^3 = 8$. Rat A drinks bottles with a 1 in the ones-place ($1,3,5,7$), Rat B drinks bottles with a 1 in the twos-place ($2,3,6,7$), Rat C drinks bottles with a 1 in the fours-place ($4,5,6,7$).

Suppose bottle 6 is poisoned, with binary address $110$. Rat C drinks from bottle 6 (since $6$ has a 1 in the fours-place) and dies. Rat B drinks from bottle 6 (1 in the twos-place) and dies. Rat A does not drink from bottle 6 (0 in the ones-place) and survives. Reading the outcome as (C, B, A) = (dead, dead, alive) = $(1,1,0)_2 = 6$ — exactly the poisoned bottle, recovered directly from which rats died without ever testing a single bottle in isolation.

What this means in practice

This puzzle is a hands-on introduction to why $\log_2 N$ shows up everywhere information needs to be pinned down efficiently — the same idea underlies error-correcting codes, hash-based reconciliation of large trade blotters, and any scheme that needs to identify one discrepancy among thousands of records without checking every record one at a time. Recognizing "this is a binary search over the test design, not over the data" is the transferable move: instead of testing bottles one at a time (linear in $N$), you're testing properties of bottles (linear in $\log_2 N$).