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
One thing I tried was weighing 50 against 50, and then taking the heavier pile and weighing 25 against 25. This didn't work, but I realized it would work if we started with 98 coins. Then you could weigh 24 against 24, with one left over. With those thoughts, here is my solution:
Weigh 49 against 49. If one pile was heavier, take that pile. It has 0 or 1 fake coin in it. If both piles were empty, take either one. It has 1 or 2 fake coins in it.
Split the pile of 49 into 24, 24, and 1. Weigh 24 against 24.
If one side is heavier than the other, then that side is made of all real coins. In order for it to have a fake coin, the other side would have to have at least two fake coins, which is not possible. Take one of the real coins.
If both sides were equal, there are two possibilities. One is that each pile had a fake coin in it (which can be ruled out if the original pile of 49 was heavier). The second is that neither pile has a fake coin (which can be ruled out if the original pile of 49 was equal to the other one).
Since we can distinguish between these two possibilities, we can choose different things in each case. In the first case, take the remaining single coin. In the second case, take any of the 48 coins.
Very nice puzzle.
|
|
Posted by Tristan
on 2013-10-19 13:20:04 |
Solution
