Eleven Deadly Pills, and One Placebo

I got asked this question in an interview when I went to work for Microsoft as an intern in 1997.  You've probably heard the version with nine pills, and the safe one is heavier.  What if there were twelve pills and you don't know if the safe one is lighter or heavier?

*   *   *

The Story:
There once was a wise scholar of an ancient land who commited a grave offense against the king, and was sentenced to death. The king, in an attempt to put the scholar's wisdom to the ultimate test, devised an ingenious riddle.


He gave the scholar 12 tiny pills. He was told that 11 of these pills were the deadliest poison, so mortal that upon taking one a man would die in seconds. The 12th pill was a mere placebo, and was completely harmless.

The scholar was also given a simple balance scale, where he might weigh the pills against each other. He was told that all the poison pills were of the exact same weight, but that the placebo weighed differently from them all. He had only THREE tries to find the placebo and live.

Things that you can assume:
1. The difference in weight of each pill is too small to descern by touch.
2. There is absolutely no way to tell by looking at the pills which one is the placebo

Solution:
There are a number of solutions to this problem. The easiest way to explain the approach is to imagine that each pill has a letter, so you can keep track of them.

Step 1:
The objective on your first try is to rule out as many pills as you can. Weigh A+B+C+D against E+F+G+H. If they do NOT balance then go to step 2. If they DO balance, then that means A through H are all poison, and your placebo is one of I, J, K, or L.

For your second try weigh I+J against A+B, which you know are both poison.
1. If they balance then you know the placebo is K or L. Weigh K against A. If K versus A balances, then L is the placebo. If they don’t balance then the placebo is K.
2. Otherwise, the placebo is I or J. Weigh I versus A. If they balance then the placebo is J, otherwise it’s I.

Step 2:
Okay, let’s take a close look at what we know. If the pill was heavy then it will be on the side that dropped. If the pill was light then it will be on the side that rose. Your next step must accomplish two objectives. You must find out if the placebo is heavier or lighter, and you must eliminate as many pills as you can. You’re going to have to get creative.

Take note of which side was heavier in step 1. Split the heavy side into two groups of two each. Next, pick any two pills from the lighter side and add one to each of the groups you made from the heavier side.

When you’re done you’ll have three groups of pills. For example, assume the left side was heavier. Your first group will have A+B+E. Your second group will have C+D+F. Your last group will be G+H.

Weigh A+B+E against C+D+F. If they do NOT balance then go to step 3. If they DO balance then your placebo is either G or H.

For your final try, weigh G against A. If G and A balance then the placebo is H, otherwise it’s G.

Step 3:
Time to dust off your skills of logical deduction. Look at which side was heavier in step 2. If A+B+E was heavier then it means that either A+B was a heavy placebo, or that F (in the right-side pan) was a light placebo. Weigh A against B. If they balance then F is the placebo. Otherwise the heavier one of either A or B is the placebo.

Otherwise, if C+D+F is heavier then it means that either C+D was a heavy placebo or that E was a light placebo. Weigh C+D. If they balance then E is the placebo. Otherwise the heavier one of either C or D is the placebo.

The key is to always pick the two from the heavier side in step 1

Example 1:
Let’s suppose F is a heavy placebo.
1. We weigh A-D against E-H. The right side is heavy.
2. We take E+F+A and weigh it against G+H+B. E+F+A sinks.
3. We weigh E against F (remember always to pick the heavy ones from step 1). We see that F is heavier, and that’s the one.

Example 2:
Let’s suppose B is a light placebo.
1. We weigh A-D against E-H. The right side is heavy, again.
2. Weigh E+F+A against G+H+B. E+F+A sinks.
3. Weigh E against F. They balance, so we know that it was the pill from the light side in step 2. That’s B


Example 3:
Suppose A is a light placebo:
1. We weigh A-D against E-H. The right side is heavy, again.
2. Weigh E+F+A against G+H+B. G+H+B is heavier.
3. Weigh G against H. They balance, so we go to the odd pill in the light pan from step 2. That’s A.