Everyone Guesses 10 Pigs. The Real Answer Is 9.

There are 1000 barrels. Exactly two contain poison. A pig dies within 15 minutes of drinking poison. The death time varies. You have one hour. Find both poisoned barrels.

The minimum is nine pigs.

Why eight pigs fail

One hour gives four test rounds:

Round 1 at 0 minutes.
Round 2 at 15 minutes.
Round 3 at 30 minutes.
Round 4 at 45 minutes.
Observe at 60 minutes.

For one pig, the final record has five states: dead after round 1, dead after round 2, dead after round 3, dead after round 4, or alive. So one pig gives five outcomes, not two.

The number of possible poisoned pairs is

C(1000,2) = 499500.

Eight pigs give at most

5^8 = 390625

outcomes. That is less than 499500. Eight cannot identify every pair.

Nine pigs give at most

5^9 = 1953125

outcomes. That is more than 499500. So nine pigs have enough information. Now we need a procedure that uses exactly nine.

Round 1: nine groups

Number the pigs P1 to P9.

Split the 1000 barrels into nine groups:

Eight groups of 112 barrels.
One group of 104 barrels.

8 * 112 + 104 = 1000.

Each pig drinks a pooled sample from its group. After 15 minutes, two cases can occur.

Case A: one pig dies

Both poisons are in the same group. That group has at most 112 barrels. Eight pigs remain. Three rounds remain.

Case B: two pigs die

The poisons are in two different groups. Each group has at most 112 barrels. Seven pigs remain. Three rounds remain.

Case A: one pig died in round 1

The poisons sit inside one group of at most 112 barrels. Eight pigs remain. Three rounds remain.

Round 2: split the 112 barrels into eight groups of 14.

Let the eight pigs drink pooled samples from the eight groups. After 15 minutes:

A1: two pigs die

The poisons are in two different groups of 14. Each group has exactly one poisoned barrel. Six pigs remain. Two rounds remain.

Use three pigs for each 14-barrel group. With two rounds, one pig has three outcomes: dies next round, dies final round, survives. Three pigs give

3^3 = 27

codes. That is more than 14. So three pigs can find one poisoned barrel inside a group of 14. Two groups use six pigs. Six pigs are available.

A2: one pig dies

Both poisons are inside the same group of 14. Seven pigs remain. Two rounds remain.

Round 3: split the 14 barrels into seven pairs.

Let the seven pigs drink pooled samples from the seven pairs. After 15 minutes:

If one pig dies, its pair contains both poisoned barrels.
If two pigs die, the two poisoned barrels are in two different pairs, one poison in each pair.

If two pigs die, one round remains. Use one pig on one barrel from the first pair, and one pig on one barrel from the second pair.

If the pig dies, that barrel is poisoned.
If the pig survives, the other barrel in that pair is poisoned.

Five live pigs remain. Two pigs are enough.

Case B: two pigs died in round 1

The poisons are in two different groups, call them A and B. Each group has at most 112 barrels. Seven pigs remain. Three rounds remain.

Use two pigs for A and five pigs for B.

Group A: two pigs classify 112 barrels

The two pigs split A into four classes:

49 barrels: neither pig drinks.
27 barrels: pig 1 drinks.
27 barrels: pig 2 drinks.
9 barrels: both pigs drink.

49 + 27 + 27 + 9 = 112.

After round 2, the number of dead pigs among these two identifies the class:

0 dead: 49 barrels remain.
1 dead: 27 barrels remain.
2 dead: 9 barrels remain.

Two rounds remain. Use ternary coding:

49 barrels need 4 pigs, because 3^4 = 81.
27 barrels need 3 pigs, because 3^3 = 27.
9 barrels need 2 pigs, because 3^2 = 9.

If a of these two pigs died, A needs 4 - a pigs for the last two rounds.

Group B: five pigs classify 112 barrels

The five pigs split B by how many of them drink from each barrel:

0 pigs: 1 pattern, 27 barrels.
1 pig: 5 patterns, 9 barrels each, 45 total.
2 pigs: 10 patterns, 3 barrels each, 30 total.
3 pigs: 10 patterns, 1 barrel each, 10 total.

27 + 45 + 30 + 10 = 112.

After round 2, the number of dead pigs among these five identifies the remaining set:

0 dead: 27 barrels remain.
1 dead: 9 barrels remain.
2 dead: 3 barrels remain.
3 dead: 1 barrel remains.

Two rounds remain. Use ternary coding:

27 barrels need 3 pigs, because 3^3 = 27.
9 barrels need 2 pigs, because 3^2 = 9.
3 barrels need 1 pig, because 3^1 = 3.
1 barrel needs 0 pigs.

If b of these five pigs died, B needs 3 - b pigs for the last two rounds.

The pig count matches

Round 2 uses

2 + 5 = 7

pigs.

If a pigs die in A and b pigs die in B, live pigs are

7 - a - b.

The final two rounds need

(4 - a) + (3 - b) = 7 - a - b

pigs. The live pigs are enough.

Ternary coding in the last two rounds

With two rounds left, one pig has three outcomes:

Dies in the next round.
Dies in the final round.
Survives.

Give each candidate barrel a k-digit ternary number. Each digit belongs to one pig.

Digit 0: that pig drinks the barrel in the next round.
Digit 1: that pig drinks the barrel in the final round.
Digit 2: that pig does not drink the barrel.

The death pattern identifies the ternary number, and therefore the poisoned barrel. A group of k pigs can handle up to

3^k

candidate barrels.

Program check

Enumerate all

C(1000,2) = 499500

possible poisoned pairs. Simulate the nine-pig procedure. Each pair produces a unique history of which pigs die in which rounds. No two pairs produce the same history.

Output:

pairs = 499500
unique histories = 499500
5^8 = 390625
C(1000,2) = 499500
5^9 = 1953125
AC
minimum pigs = 9

Eight pigs fail because

5^8 = 390625 < 499500 = C(1000,2).

Nine pigs work because the construction above identifies both poisoned barrels within one hour.

Minimum number of pigs: nine.