Maths Olympiad Prep

Library / /2 of 17

Combinatorics Difficulty 5.4 AIME, harder Prove it Argentina

Given are 16 balls with weights 1313, 1414, 1515, \ldots, 2828 grams. Determine the balls with weights 1313, 1414, 2727, 2828 grams, by using a two-pan balance at most 2626 times.

Solution

One can find the lightest ball 1313 via direct elimination by pairs: we make 88 pairs and determine the 88 lightest on each pair, now we make 44 pairs and determine the lightest on each pair, then we select the two lightest and finally, the ball with the minimum weight. This takes 8+4+2+1=158+4+2+1=15 attempts. Ball 1414 is among the ones eliminated by ball 1313 in the process. There are 44 of them; 1414 is the lightest one, and it can be found by direct elimination again with 2+1=32+1=3 attempts.

Observe now that 2828 is the only ball heavier than 1313 and 1414 combined. Likewise 2727 is the only ball with the same weight as 1313 and 1414 combined. In addition, ball 2828 is among the eight losers in the first eight uses of the balance. Let them be B1,,B8B_1, \ldots, B_8. (It could be less if 1414 was eliminated by 1313 in the first eight uses of the balance.)

For each i=1,,8i = 1, \ldots, 8 compare ball BiB_i with the group 1313, 1414. One of these eight attempts will find ball 2828. If there is equilibrium at one of the seven remaining attempts, ball 2727 is found too. Otherwise 2727 is a winner in the first round, which is possible only if it was compared with 2828 at the first round. Therefore, because 2828 is already known, so is also 2727; no further attempts are needed. The task is solved with 15+3+8=2615+3+8=26 attempts.

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 and solution reproduced as published; topic and difficulty added by this site.