Among 100 coins exactly 4 are fake. All genuine coins weigh the same; all fake coins, too. A fake coin is lighter than a genuine coin.
How would we find at least one genuine coin using two weighings on a balance scale?
Source: 2010 Euler math Olympiad in Russia- authored by A.Shapovalov
Let R=real coin and F=fake coin
Pick 4 coins at random and put two on each side of the balance. If they DO NOT balance, the possibilities are:
RR vs. RF
RF vs. FF
RR vs. FF
Then take only the coins on the heavy side, and balance them against each other. The heavy side will be a Real coin, or both will be Real if the scale balances.
The trickier part is what to do when the original four coins DO balance the scale. The possibilities are:
FF vs. FF
RR. vs. RR
In this case, move all four coins to one side and pick four additional
coins for the other side. Possibilities are:
FFFF vs. RRRR
RRRR vs. RRRF
RRRR vs. RRFF
RRRR vs. RFFF
Note that the heavier side always has four Real coins. QED
Posted by Kenny M
on 2013-10-18 20:35:05