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 33-33 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 2013-10-20 13:24:15 |
Think I've got it
