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
Thanks to the hint and an insight by Mrs. xdog.
Weigh 33 against 33.
Say they don't balance. Then the heavier side has either 0 or 1 light coins. Pick two coins from the heavier side and weigh them. If they balance they're both normal, otherwise the heavier is normal.
If the 3333 weighing balances, each side can contain 0,1, or 2 light coins. Here I complained to Mrs. xdog that I couldn't match 34 against 33. She replied "Well, 33 and 1 equals 34". Yes, yes it does.
Label the groups of 33 X and Y, the group of 34 Z. Take a coin from X and add it to Y.
Distribution of light coins
XYZ XYZ
Case before after
1 004 004
2 112 112
3 112 022
4 220 220
5 220 130
Case 1, Y>Z, transferred coin normal
Case 2, Y>Z, transferred coin normal
Case 3, Y=Z, remaining X normal
Case 4, Y<Z, all Z normal
Case 5, Y<Z, all Z normal

Posted by xdog
on 20131020 13:24:15 