Mice and Test Tubes

What’s going on

A lab has 240 test tubes that look exactly alike. One of them was filled by mistake with a liquid that is poisonous to people, and it must be found. Lab mice can help: for a mouse the poison is harmless, except that a single drop turns its fur bright orange within a day. There are 8 mice. How fast can you find the tube?

The slow way

The natural plan is to split the tubes into groups. Give each mouse a mixture of drops from its own group of tubes, and keep one group untested. After a day at most one mouse is dyed, and you know which group holds the poisoned tube. Nine groups of at most 27 tubes, then repeat with the 7 mice left: groups of 3 or 4, then a single tube. That takes three days.

The plan wastes something. On each day it lets at most one mouse change colour. But every mouse is a yes-or-no answer, and we only read one of them.

The fast way: binary

Number the tubes from 0 to 239 and write each number in binary with 8 digits. Tube 154, for example, is 10011010. Give each mouse one digit place: mouse 1 gets the 128s place, mouse 2 the 64s, and so on down to mouse 8 with the 1s.

Now each mouse drinks a drop from every tube that has a 1 in its place. So each mouse drinks from roughly half of the tubes, and each mouse from a different half. The next day, look at the mice: dyed means 1, clean means 0. If the poisoned tube is 154, exactly mice 1, 4, 5 and 7 drank it, so the mice read 1 0 0 1 1 0 1 0, and 128 + 16 + 8 + 2 = 154.

One day is enough, because 8 digits can write 2⁸ = 256 different numbers, more than 240. Even tube 0, which no mouse drinks from, gets its own answer: no dyed mice at all.

Try it in the scene above: press Next day, then Read the mice. Click a mouse to see which tubes it drinks from, and hover over a tube to see its number in binary.

Fewer mice, more days

What if there are only 5 mice? Then one day is not enough: five yes-or-no answers make only 2⁵ = 32 patterns. But with two days, each mouse can say three things: dyed on day one, dyed on day two, or never dyed. So write the tube numbers in base 3, with digits 0, 1 and 2. On day one each mouse drinks from the tubes with a 1 in its place; on day two, from the tubes with a 2. Five mice give 3⁵ = 243 patterns, just enough for 240 tubes. Tube 154 is 12201 in base 3: mouse 1 is dyed on day one, mice 2 and 3 on day two, mouse 4 never, and mouse 5 on day one.

A mouse that was dyed on day one has nothing left to tell us, and it does not need to: every remaining suspect has a 1 in its place.

In general, with N days each mouse has N + 1 possible answers, so m mice tell apart at most (N + 1)ᵐ tubes. The fewest mice is the smallest m for which (N + 1)ᵐ reaches the number of tubes. For 240 tubes that is 8 mice in one day, 5 in two days, and 4 in three days (4⁴ = 256). Change the Days setting to see each.

No plan can beat this, not even one that changes its mind after each day: the whole experiment ends with every mouse reporting one of N + 1 things, and different tubes must end with different reports.

Try it yourself

1. A thousand tubes

How many mice do you need to find one poisoned tube among 1,000 in a single day?

Answer

10. Nine mice give 2⁹ = 512 patterns, too few; ten give 2¹⁰ = 1,024.

2. Read the mice

With 8 mice and one day, mice 2, 3 and 8 are dyed. Which tube was it?

Answer

The mice read 0 1 1 0 0 0 0 1, which is 64 + 32 + 1 = 97.

3. One mouse, many days

You have just one mouse but plenty of time. How many tubes can it check in 6 days, and how?

Answer

7 tubes. Give it tube 1 on day one, tube 2 on day two, and so on up to tube 6 on day six. The day it turns orange names the tube; if it never does, it is the seventh. This is the formula with m = 1: (6 + 1)¹ = 7.

Go deeper

• The same idea, called group testing, was proposed during the Second World War by the economist Robert Dorfman to screen blood samples in pools instead of one by one. Pooled tests were used again for COVID-19.
• Information theory gives the same count: one yes-or-no answer is one bit, and picking one of 240 tubes takes log₂ 240 ≈ 7.9 bits, so 8 mice. A mouse watched for several days gives one of N + 1 answers, which is worth more than one bit.