Some time ago, a friend asked for my help with a puzzle:

There are 1,000 buckets, one of them contains poison, the rest of them are filled with water. They all look the same. If a pig drinks that poison, it will die within 30 minutes. What is the minimum number of pigs do you need to figure out which bucket contains the poison within one hour?

Since I was familiar with *similar* problems, I quickly replied: **the answer you’re looking for is 32** (the rounded square root of 1000). The procedure looks like this: the first half hour, split all 1000 buckets in 32 groups of 32 buckets. Have the first pig drink a drop from *every bucket* from group #1, and so on. Half an our later one pig will die, so we’re left with 32 candidate buckets (and 31 pigs) for the second half hour. Then, have all pigs drink from one bucket. This should find the poison (if none of them perish, the poison is in bucket #32). Proud at my problem solving skills, quickly rested my case and focused my attention in something else.

A few weeks later, I realized that **I was wrong**. 1000 buckets can be binary encoded with 10 bits (log 2, 1000) = 9,96 -> **10 pigs will suffice**. The procedure is explained below for 8 buckets and 3 pigs (10 pigs solve 1024 buckets).

` Pig1 Pig 2 Pig 3`

Bucket 1: 0 0 0

Bucket 2: 1 0 0

Bucket 3: 0 1 0

Bucket 4: 1 1 0

Bucket 5: 0 0 1

Bucket 6: 1 0 1

Bucket 7: 0 1 1

Bucket 8: 1 1 1

There was a disturbing fact though: the procedure solves the problem in half an hour, and we have an entire hour to use. However, after finding a a solution to a *similar* problem in the comments section of the original post, I ignored this annoying fact and quickly jumped into the conclusion that the solution was actually 10.

Long story short, **I was wrong, again**. There are 2 better solutions:

**Solution with 9 pigs**: binary encoding, but in two “rounds” of 512 buckets.

**Solution with 7 pigs**: use ternary encoding instead of binary. The “trits” (as opposed to bits) represent 3 states: “dead in the first half hour”, “dead in the second half hour” and “survivor”. Using this technique, 7 pigs can solve up to 2187 buckets (3^7).

**A dangerous cognitive bias**

This sequence of failures have a common denominator: I tried to match the problem with the most similar pattern I knew, and quickly jumped into conclusions. As Daniel Kahneman says in his marvelous book Thinking Fast and Slow:

“A failure to check is remarkable because the cost of checking is so low”

In my case, I only had to check the comments section of the page! I almost answered by intuition. Since everything “looked right” the lazy left side of the brain failed to ring the alarm… 4 times.

To illustrate this point, Kahneman gives the following example. Don’t try to solve it but listen to your intuition:

A bat and ball cost $1.10

The bat costs one dollar more than the ball

How much does the ball cost?

They tested this simple puzzle on thousands of university students. More than 50% of students at Harvard, MIT and Princeton gave the intuitive -incorrect- answer: 10¢. The right answer is $1.05 and 5¢.

“A few seconds of mental work, with slightly tensed muscles and dilated pupils, could avoid an embarrassing mistake.”

This cognitive bias “force a situation into a known pattern and quickly jump into conclusions” is quite dangerous in a Technology team. Often the size of the inefficiency of a suboptimal solution is in the range of “32 vs 7 pigs”. In a large system, this cost could be huge, both financial and in terms of User Experience.

My first hand encounter with this dangerous bias made me tweak the “left side alarms” and strive to minimize the negative effects. After a while, it’s paying off. Hope you find it useful too.

Daniel Rabinovich

Hi! Interesting lecture and excericise for my bqb trip

I think I could contribute with 2 different solutions

Solution #1

The question is “What is the minimum number of pigs do you need to figure out which bucket contains the poison within one hour?”

I will interpret need=”need to let die” instead of “need to have available”

Suppose that you dont even have seven pigs of your own, but you could borrow as many as you need from a friend of yours .

Maybe in that case what you would try to optimize is the piggy casualties instead of just availability, because you should pay for those being killed.

Have a look at the pig lives lost:

For the binary encoding solution 4,5 pigs will die avg, 9 top.

For the sqr root solution you make 2 widow pigs at most.

But if you could borrow 500 pigs, expected casualties would be 0.99 avg, and exactly 1 at most…. and you will have to pay for one pig, or none if you are lucky

Solution #2

An even better solution for pigs

Taking into account (“imaging” suit better)that pigs would die exacly half an hour after having drunk the poisson, why not just expose one pig to every bucket during the first half hour. Then just wait til it dies during the second half and map back the bucket number to that being drunk 30 mins before.

In this way you need a very accurate chronometer, and a die prompt pig 🙂

You use 1 pig. You kill 1 pig at most (avoid to give it bucket #1000 and maybe it would make it back home)

……….

Finally i am not sure about the ternary encoding solution. Pigs would die during the first half only if they drank the poison in minute 0.

In that solution *you need every pig to be able to get “death in first half ” status*

so you need to test every pig against the buckets in t=0 and therefore you could even reach minute 30 with all 7 pigs dead and the venom bucket unveiled. You need 2 more pigs i think.

Solutions #1 and #2 are iteresting!! But to a different problem 🙂

wrt ternary encoding, would you agree that 1 pig can solve 3 buckets?

Professor at Southern Oregon University

The answer is one. If one pig drinks from the poison and dies, you know which pale holds the poison. That’s the minimum number. It’s not effective, but it meets the criteria for the question.

My bad, question is a bit imprecise. When it says “figure out”, it means “to know without any margin of error”. Your can’t achieve that, you get the correct answer only if you get lucky. Best! Dani.-