One Poisoned Barrel

  • Hard
  • Measuring and weighing
  • Tests: Reading each tester as one binary digit

The puzzle

A cellar holds 1000 barrels and exactly one is poisoned. The poison kills in exactly one month, in any dose.

You have one month and a number of testers who may each sip from as many barrels as you like. What is the smallest number of testers that always identifies the barrel?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Each tester gives you one bit at the end of the month: died, or did not.

Hint 2

How many different outcomes can n testers produce between them?

Show the answer Hide the answer

Ten. Number the barrels 0 to 999 in binary and have tester k sip from every barrel whose k-th bit is 1.

How to get there

After a month each tester is either dead or alive - one bit each. Ten testers give 2^10 = 1024 distinct outcomes, which is just enough to name 1000 barrels; nine would give 512, which is not.

Write each barrel number in 10-bit binary. Tester k drinks from every barrel with a 1 in position k.

At the end, read the dead testers as 1 and the living as 0. Those ten bits spell out the number of the poisoned barrel exactly.

The technique worth keeping

Count the information before designing the test: n yes-or-no answers can distinguish at most 2^n cases. Once the bound is known, binary labelling is usually the construction that meets it.