Finding the Poison Bottle with Minimum Rabbits: Binary Encoding Explained

Story Origin

There are 1,000 bottles of liquid, one of which is poison; a single drop kills a rabbit within a day. The challenge is to determine the poisonous bottle using as few rabbits and as little time as possible.

Condition Analysis

The poison can be given to multiple rabbits, so the problem becomes a trade‑off between time (how quickly we get a result) and space (how many rabbits we are willing to sacrifice).

Pure‑time approach: use 1,000 rabbits, each testing one bottle, yielding a result in 1 day.

Pure‑space approach: use a binary‑search‑style halving method, consuming at most one rabbit per round and requiring up to 10 days.

Balanced (Middle‑Way) Strategies

By combining the two extremes, we can reduce both resources. For example, with 9 rabbits we can split the 1,000 bottles into 10 groups each round, finishing in 3 days (1000 → 100 → 10 → 1). With 2 rabbits we can split into 3 groups each round, requiring 7 days, following the formula d = log_a(N) where a is the number of groups and N is the bottle count.

Computer‑Thinking Solution (Binary Encoding)

A far more efficient method uses binary representation. Number the bottles 1‑1000 and assign each of 10 rabbits a binary digit (1‑10). For each bottle, write its index in 10‑bit binary; a rabbit drinks from a bottle if the corresponding bit is 1. After one day, the pattern of dead rabbits directly yields the binary code of the poisonous bottle, identifying it in a single test with only 10 rabbits.

This approach achieves the optimal balance: minimal time (1 day) and modest space (10 rabbits), demonstrating how algorithmic thinking can turn a seemingly complex puzzle into a simple binary decoding problem.