Finding the Poisoned Bottle Among 1000: Why 10 Mice Are Enough

Core Pain Point: Why 10 Mice?

Most candidates try a sequential "one mouse per bottle" approach, which seems impossible for 1000 bottles. The interview actually tests knowledge of information theory and binary storage.

Binary Insight

Each mouse can be in one of two states: dead (1) or alive (0). The poisoned bottle has a unique index. Ten mice provide 2^10 = 1024 possible state combinations, which exceeds the 1000 possible bottle numbers.

Step 1: Label Wines with Binary Codes

Bottle 1 → 00 0000 0001 Bottle 2 → 00 0000 0010 Bottle 3 → 00 0000 0011 …

Bottle 1000 →

11 1110 1000

Step 2: Prepare 10 Test Pools

Create ten separate pools, each corresponding to one bit position (1‑10). For every bottle, drop a tiny sample into each pool whose bit is 1.

Bottle 1 (binary 00 0000 0001) adds a drop only to pool 1.

Bottle 2 (binary 00 0000 0010) adds a drop only to pool 2.

Bottle 3 (binary 00 0000 0011) adds drops to pools 1 and 2.

…

Bottle 1000 (binary 11 1110 1000) adds drops to pools 4, 6, 7, 8, 9, 10.

After this distribution each pool contains a mixture of samples from many bottles, but the pools remain isolated.

Step 3: Parallel High‑Concurrency Testing

Assign each of the ten mice to a distinct pool and let them drink simultaneously. Because the test is performed in one round, the total time is constant.

After the poison’s latency, record which mice died (1) and which survived (0). The resulting 10‑bit pattern directly maps to the binary label of the poisoned bottle.

If only mouse 1 dies → pattern 00 0000 0001 → bottle 1.

If mice 1 and 2 die → pattern 00 0000 0011 → bottle 3.

If mice 4, 6, 7, 8, 9, 10 die → pattern 11 1110 1000 → bottle 1000.

The death combination is the exact address of the poisoned wine; no extra mice are required.

Technical Takeaways

Bitmap & Bloom Filter: Using 10 bits to represent a large set mirrors how bitmaps and Bloom filters compress massive data with minimal space.

Space‑for‑Time Trade‑off: One mouse sequentially testing 1000 bottles trades time for space, which is unacceptable in high‑performance systems. Ten mice achieve constant‑time identification by expanding the state space.

Power of Bit Operations: Mastery of &, |, ^, << etc. is essential; this puzzle probes a candidate’s comfort with low‑level binary manipulation.

In future interviews, remember that many problems are disguised tests of binary thinking and information‑theoretic efficiency.