Maths Olympiad Prep

Library / /8 of 15

Combinatorics Difficulty 6.1 National Olympiad Prove it Argentina

Twenty undistinguishable coins are arranged in a row. One of them weighs 99 grams and the next coin to the right weighs 1111 grams. The remaining 1818 coins have weight 1010 grams each. Find the 1111 gram coin with 33 weightings on a two-pan balance without weights.

Solution

On the first attempt compare two groups of 99 coins each: G1=1,3,5,7,9,11,13,15,17G_1 = 1,3,5,7,9,11,13,15,17 and G2=2,4,6,8,10,12,14,16,18G_2 = 2,4,6,8,10,12,14,16,18. Note that the 99 grams coin AA and the 1111 grams coin BB cannot be on the same pan as their positions are consecutive, hence of different parity.

If there is equilibrium we claim that, moreover, neither AA nor BB is on the pans, i.e. they are at positions 1919 and 2020. Indeed suppose that AA or BB is on one of the pans. Equilibrium is impossible with exactly one exceptional coin; the other one must be on a pan too. Moreover for equilibrium both of them must be on the same pan; however we remarked that this is not so. Thus AA and BB are at positions 1919 and 2020, and since BB is the right neighbor of AA, we find that the 1111 grams coin is the last one. Note that the case of equilibrium needs no further attempts.

Let G1G_1 be lighter than G2G_2. Then AG1A \in G_1. Indeed if AG1A \in G_1 then G1G_1 has only 1010 grams (it cannot contain BB). Hence G1G_1 is lighter only if BG2B \in G_2. So BB is at even position 2,4,...,182, 4, ..., 18. But then AA is at the previous odd position 1,3,...,171, 3, ..., 17, i.e. it is in G1G_1 contrary to the assumption.

Similarly let G1G_1 be heavier than G2G_2. Then AG2A \in G_2. Otherwise G2G_2 has only 1010 grams coins and it is lighter only if BG1B \in G_1. So BB is at an odd position 3,5,...,173, 5, ..., 17; note is not 11 as BB is preceded by AA. But then AA is at the previous even position 2,4,...,162, 4, ..., 16, i.e. AG2A \in G_2, contrary to the assumption.

So in the case of non-equilibrium the first attempt finds a group of 99 coin with 88 of them having the same weight and the last one lighter. It is known how to find the lighter coin with 22 attempts. Divide the coins into 33 groups of 33 and compare two groups. Regardless of the outcome this determines a group of 33 coins containing the lighter one. It remains to compare two coins from GG. Regardless of the outcome the lighter coin will be identified.

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.