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.»
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.