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 14 must all be light and so 1 is light.
If 1+2+3+4 > 5+6+7+8 then 14 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 18 to 916.
In this case, they *can't* be equal because one side is all light and the other side is all heavy. If 18 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 20151230 12:08:39 