I have two sets of 8 coins. In one set the coins weigh 30g each, in the other set the coins weigh 31g each.
Unfortunately they got mixed together in one big pile of 16 coins. I want to identify one coin. It can be from either set.

(Easy) Using a balance scale, identify a coin in four weighings.

(Hard) Identify a coin in just three weighings.

Label the coins 1 - 16, labeling the specific coin of interest 1.

Compare 1+2 vs 3+4. There are three possible outcomes: <, =, >

If 1+2 < 3+4 then 1 and 2 are either both light or are one heavy and one light. In this case, use the 2nd weighing to compare 1 and 2.
If 1 <= 2 then 1 is light, otherwise it's heavy

Analogously, if 1+2 > 3+4 then 1 and 2 are either both heavy or are one light and one heavy. Again, compare 1 and 2 with the 2nd weighing.
If 1 >= 2 then 1 is heavy, otherwise it's light

It's more interesting if 1+2 = 3+4. In this case as the 2nd weighing, compare 1+2+3+4 to 5+6+7+8, knowing that all four of the left coins are identical (but not whether they're light or heavy.)
There are still three possible outcomes.

If 1+2+3+4 < 5+6+7+8 then 1-4 must all be light and so 1 is light.
If 1+2+3+4 > 5+6+7+8 then 1-4 must all be heavy and so 1 is heavy.

If 1+2+3+4 = 5+6+7+8 then they're all identical, and we need that third weighing.  Compare 1-8 to 9-16.
In this case, they *can't* be equal because one side is all light and the other side is all heavy. If 1-8 is the light side, 1 is light, otherwise it's heavy.

So, two weighings are sufficient unless you get unlucky and manage to pick all 8 of the same coin, but the third weighing is still there to provide the final piece of information to answer the question.

Posted by Paul on 2015-12-30 12:08:39