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 N and L indicate normal and light coins.
Set aside 2 coins and label them 1 and 2.
Split the remaining 98 coins and weigh 49 against 49.
Say they balance. Then each side of the scale must contain 1 or 2 L's, so both sides together contain 2 or 4 L's, which means 1 and 2 are either NN or LL.
Select 2 different coins, call them 3 and 4, from the same side of the balance and weigh them against 1 and 2.
If 12 = 34 or 12 > 34 coins 1 and 2 = N since NN = NN, NN > NL, NN > LL.
If 12 < 34 any of the 47 remaining coins of the group from which 3/4 were chosen = N, since LL < NN and LL < LN.
If the first weighing doesn't balance, then the heavy side contains either 0 or 1 L coins. Simply weigh two coins from the heavy side. If they balance both are N, otherwise the heavier is N.
|
|
Posted by xdog
on 2013-10-18 23:21:40 |
Solution
