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
After seeing Ady's hint I solved the problem. But after playing around with it further, I found a solution which guarantees finding 13 genuine coins in two weighings.
First, divide the four coins in groups: A=13, B=16, C=29, D=42. Weigh A+B vs C.
Case 1: A+B != C. The heavier side has at most one fake coin. From that heavier side take a 13 vs 13 weighing. If equal then all 26 are genuine; if unequal then the heavier set of 13 are all genuine.
Case 2: A+B=C. A+B has 0, 1, or 2 fakes; C has 0, 1, or 2 fakes; and D has 0, 2, or 4 fakes. Weigh A+C vs D.
Case 2.1: A+C<D. D cannot be greater with 2 or 4 fakes, therefore all the coins in D are genuine, take any 13.
Case 2.2: A+C=D. A+C and D have the same number of fakes and at least two fakes between them (B has at most 2 fakes), which implies that A+C and D have at least one fake each. But D must have an even number of fakes which forces all four fakes to be found in A+C and D (two on each side). Thus, all the coins in B are genuine, take any 13.
Case 2.3: A+C>D. D has either 2 or 4 fakes. If D has 4 fakes, then all of A,B,C are genuine. If D has 2 fakes, then A+B has 1 and C has 1; but for A+C>D the fake in A+B must be in B otherwise the weighing would balance. In either case all the coins in A are genuine, take those 13 coins.
Finding 13 Genuine Coins
