All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Take the right one (Posted on 2013-10-18)
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

Comments: ( Back to comment list | You must be logged in to post comments.)
 Finding 13 Genuine Coins | Comment 16 of 18 |

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.

 Posted by Brian Smith on 2013-10-20 19:12:35

 Search: Search body:
Forums (1)