Maths Olympiad Prep

Library / /180 of 196

Combinatorics Difficulty 6.4 National Olympiad Prove it Soviet Union

Problem:

You are given 14 coins. It is known that genuine coins all have the same weight and that fake coins all have the same weight, but weigh less than genuine coins. You suspect that 7 particular coins are genuine and the other 7 fake. Given a balance, how can you prove this in three weighings (assuming that you turn out to be correct)?

Solution

Solution:

Let the coins you suspect to be genuine be G1G_1, G2G_2, ..., G7G_7, and the suspected fakes be F1F_1, F2F_2, ..., F7F_7.

First, weigh F1F_1 against G1G_1. Assuming F1F_1 weighs less, you have proved that F1F_1 is fake and G1G_1 genuine.

Second, weigh F1F_1, G2G_2, G3G_3 against G1G_1, F2F_2, F3F_3. Assuming the first three weigh more, you have proved that they include more genuine coins than the second three. But the second three includes one genuine coin (G1G_1) and the first three includes one fake (F1F_1), so you have proved that G2G_2 and G3G_3 are genuine and F2F_2 and F3F_3 fake.

Finally, weigh F1F_1, F2F_2, F3F_3, G4G_4, G5G_5, G6G_6, G7G_7 against F4F_4, F5F_5, F6F_6, F7F_7, G1G_1, G2G_2, G3G_3. Assuming the first group weighs more, it must include more genuine coins and hence just four genuine coins. Similarly, the second group must include four fakes. So you have proved the identity of the remaining coins.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.