Group testing is born
Robert Dorfman described pooled testing in a short paper, "The Detection of Defective Members of Large Populations", in the Annals of Mathematical Statistics. He later became a professor of economics at Harvard.
The king's feast is in 24 hours. The cellar holds 1,000 bottles of wine, and exactly one of them is poisoned. The poison is slow: a rat that drinks even a drop dies about 20 hours later, never sooner. So you get only one round of tasting: all the rats drink at the same time, and then you wait. Each rat can sip from as many bottles as you like. How many rats do you need to find the poisoned bottle for sure?
It looks as if you need one rat per bottle, so 999. But each rat answers one yes-or-no question, and 10 such answers tell apart 2¹⁰ = 1,024 cases. Write the bottle numbers in binary, and the dead rats spell out the number of the poisoned one.
This puzzle often turns up in collections of interview puzzles for programmers and analysts. Behind it stands a whole branch of mathematics, group testing, and the same idea that every digital code relies on.
The cellar holds 1,000 bottles, numbered 1 to 1,000. Exactly one is poisoned. They all look, smell and taste the same.
Even a tiny drop is lethal, but it is slow: a rat dies about 20 hours later, never sooner. The feast is 24 hours away, so there is no second try.
Each rat can be given a drop from any set of bottles: one, ten, five hundred. A rat that drank no poison stays alive.
All rats drink at the same time. After 20 hours you see which of them are alive and which are dead, and from that you must name the poisoned bottle. Not guess it: know it for sure.
What is the smallest number of rats that guarantees you find the poisoned bottle?
"One rat per bottle: 999 rats, and the last bottle needs no test"
Some people save a little and say "500" or "about 100". In fact 10 rats are enough, and 9 are not enough with any strategy. The trick is that each rat drinks from many bottles, and what matters is exactly which group of rats dies.
1,000 bottles, one poisoned, one round of tasting. Lock in the smallest number of rats that, in your view, guarantees success.
A breakdown of your answer will appear here.
Take a smaller cellar. In the table each row is a rat and each column a bottle. Click a cell and that rat will drink from that bottle. When your strategy is ready, press "Break my strategy": the page looks for two bottles after which exactly the same rats die. If there are such bottles, you cannot tell them apart.
Let's compare how often a strategy names the right bottle, depending on the number of rats. If several bottles give the same outcome, you pick one of them at random. Lines show the exact probability, dots show the success rate in the simulation.
The rat axis is logarithmic, so 10 and 999 fit on one chart. The random strategy is drawn afresh after every N/5 poisonings (N is the number of bottles): each rat drinks from each bottle with probability 1/2.
The key is not how many bottles you test but how many different outcomes the rats can produce. Here are five ways to see it.
Giving a rat drops from a set of bottles asks: "Is the poison in this set?" A dead rat means yes, a live one means no. That is one answer out of two possible, which is one bit. Ten rats give ten answers at once.
Give the rats weights 1, 2, 4, …, 512. The rat with weight 2k drinks from the bottles whose binary number has a 1 in the 2k place. Then exactly the rats whose weights add up to the poisoned bottle's number will die.
Each rat is either alive or dead, so m rats give at most 2m different outcomes. If there are more bottles than outcomes, two bottles must share an outcome: that is the pigeonhole principle. With 9 rats there are 512 outcomes and 1,000 bottles, so no strategy with 9 rats can guarantee success.
When each rat drinks from just one bottle, at most one rat dies. 999 rats could produce 2999 different outcomes, a number with 301 digits, yet the strategy uses only 1,000 of them: "rat k died" or "nobody died". Nearly every rat almost surely says no, and its answer tells you almost nothing.
In 1948 Claude Shannon proposed measuring information by how much an answer reduces uncertainty. An answer to a question where yes and no are equally likely gives exactly 1 bit, and an answer you can almost surely predict gives almost nothing. Picking one bottle out of 1,000 takes log₂ 1000 ≈ 9.97 bits. In the binary strategy each rat dies in about half the cases (for 489 to 500 bottles of the 1,000), so it delivers almost a full bit, and 10 rats are just enough.
The binary strategy not only reaches the bound, it also needs no computing during the tasting: the rats' schedule is written in advance, and the answer is read off as a number. With N bottles, ⌈log₂ N⌉ rats are enough, and fewer cannot work.
The rat puzzle opens the door to three worlds. In mathematics it grows into coding theory. In logic it becomes the game of twenty questions. In practice the same trick saves millions of blood tests and helps programmers hunt bugs.
Mathematics
Say the poison kills within 10 hours. Then a day fits two rounds: one at the start, one 10 hours later, with results visible by hour 20. Now a rat has three possible fates: dead after round 1, dead after round 2, or alive. Write the bottle number in base 3: digit 1 means "the rat drinks from this bottle in round 1", 2 means "in round 2", and 0 means "never drinks it".
With m rats there are 3m outcomes. 3⁶ = 729 is too few for 1,000 bottles, while 3⁷ = 2,187 is enough, so 7 rats are needed. In general, with r rounds each rat has r + 1 outcomes, and you need ⌈logr+1 N⌉ rats. A rat that died in round 1 cannot drink in round 2, but that does no harm: its digit is already known.
8 bottles, 3 rats, the binary strategy. Pick two poisoned bottles.
With two poisoned bottles, a rat dies if it tasted at least one of them. Binary numbers fail here: the outcome only shows in which places at least one of the two numbers has a 1, and that does not pin down the pair.
1,000 bottles form C(1000, 2) = 499,500 pairs. There must be at least as many outcomes as pairs; 2¹⁸ = 262,144 is too few while 2¹⁹ = 524,288 is enough, so at least 19 rats are needed. This is only a lower bound, and reaching it is hard. For 8 bottles the bound is 5 (28 pairs, 2⁵ = 32), yet a full search over all strategies shows that 6 rats are actually needed.
This is how the rat puzzle turns into group testing: how to check many samples with few pooled tests when several of them may be "bad".
16 bottles, 7 rats. Pick the poisoned bottle, then click any rat to make it "lie": die for no reason, or survive the poison.
For 16 bottles 4 rats are enough, but if one of them may "lie", you can no longer trust the outcome. The naive defence: triple every rat and go with the majority, which takes 12 rats. In 1950 Richard Hamming found a better way: 4 rats carry the bottle number, and 3 more check the parity of different groups. 7 in all.
Why exactly 7? Each bottle has to "own" 8 outcomes: the honest one and 7 in which one rat lied. 16 · 8 = 128 = 2⁷, so 7 rats are a perfect fit, with not a single outcome to spare. The three checks form a "syndrome": a three-digit binary number that names the rat that lied.
Logic
The page will find it in at most 10 yes-or-no questions.
In twenty questions one player thinks of an object and the others find it with yes-or-no questions. If every question splits the options in half, 20 questions tell apart 2²⁰ = 1,048,576 objects. Programmers call this binary search.
There is one important difference. In the game you choose the next question knowing the previous answers. The rats all answer at once, so the questions must be fixed in advance. Surprisingly, for a single poisoned bottle this costs nothing: both ways need 10 questions. The only difference is time: 10 rounds of 20 hours each against one.
Practice
In 1943 the economist and statistician Robert Dorfman proposed testing men drafted into the US Army for syphilis like this: mix the blood of k people and run one test. If it is negative, all k are healthy. If positive, everyone in the group is tested separately. That costs 1/k + 1 − (1 − p)k tests per person, where p is the share of infected people.
For syphilis the idea was never put to use back then: according to Du and Hwang's book on group testing, the Wassermann test lost accuracy once eight or nine samples were mixed. But in 2020, during the COVID-19 pandemic, the Technion and Rambam hospital in Israel showed that a PCR test finds one positive sample in a mix of 32 or 64.
And programmers hunt for a "poisoned bottle" every day with git bisect: it finds the commit that broke a program by binary search. Among 1,000 commits that takes about 10 steps, though each step depends on the previous one, as in twenty questions.
Robert Dorfman described pooled testing in a short paper, "The Detection of Defective Members of Large Populations", in the Annals of Mathematical Statistics. He later became a professor of economics at Harvard.
John Tukey coined "bit", short for "binary digit", in a Bell Labs memo dated 9 January 1947. Claude Shannon was the first to use the word in print, in his 1948 paper "A Mathematical Theory of Communication".
Richard Hamming worked at Bell Labs and was frustrated by an error-prone punched card reader. The result was the (7,4) code: 4 data bits, 3 parity bits, and any single error gets corrected.
Twenty questions dates back at least to the 18th century, and in the 1940s it became a popular radio quiz show in the US. If each question halves the options, 20 questions tell apart 2²⁰ objects.
In March 2020, researchers from the Technion and Rambam hospital reported that a pooled PCR test detected the coronavirus in a mix of 64 samples with only one positive among them. Only samples from positive pools were then tested one by one.
The git documentation has an example: "Bisecting: 675 revisions left to test after this (roughly 10 steps)". It is the same binary search: each "good" or "bad" answer cuts off half the commits.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.