Section 28.2

Encoding and Group Testing

Poisoned wine and binary encodings, identifying a light switch, prisoners' counting protocols.

Toolkit

Both puzzles rest on information-counting: $k$ independent binary tests (or bits of state) distinguish at most $2^k$ possibilities, so the minimum number of tests/bits needed to identify one item among $N$ is $\lceil \log_2 N\rceil$ .

Encode each candidate (switch, keg) by its binary index; let test/question $i$ probe exactly those items whose $i$ -th bit is $1$ . The resulting pattern of outcomes (on/off, dead/alive) reconstructs the index bit by bit.
A single physical channel can carry multiple bits if it has several distinguishable states (e.g. on/off $\times$ hot/cold gives 4 states from one bulb).
Any single yes/no answer splits the outcome space into two parts; the best you can guarantee is success on whichever part you land in, so with $2^n$ equally likely sequences and one question, correct-guess probability is at most $2/2^n$ .
For counting/consensus protocols among $n$ anonymous agents with a shared binary signal, assign one agent the role of counter who resets the signal each time it is tripped; every other agent trips it exactly once, so the process terminates after $n-1$ resets.

Problems