Maths Olympiad Prep

Library / /22 of 25

Combinatorics Difficulty 4.5 AIME Prove it Japan

On the left scale of a balance 4 weights weighing 2222, 2424, 2626, 2828 grams each are placed and on the right scale 4 weights weighing 2323, 2525, 2727, 2929 grams each are placed. This balance gets tilted toward the side having heavier total weight, and settles in equilibrium position when the total weights of both sides are equalized. Suppose we repeat a procedure of removing a weight from the scale on the tilted side, until the equilibrium is reached. How many different ways of removing the weights are there if the equilibrium is reached only when all the weights are removed?

Solution

Suppose we keep on removing weights from the scale on the tilted side, and instead of stopping when the balance gets in the equilibrium position with some weights still left on the scales, remove another weight from the left-side scale and keep on removing weights from the tilted side again until there are no more weights to be removed. Then the total number of ways of removing weights is given by (4!)2=576(4!)^2 = 576, which is equal to the total number of ordering the removals of weights from each of the scales. The desired number we seek as the answer to the problem is obtained by subtracting from 576576 the number of ways where equilibrium is reached with some weights still remaining on the scales.
Suppose we denote by rr the ratio (taken as no less than 11) of the numbers of weights left on the two scales when equilibrium is reached, then rr is no more than the ratio 2922\frac{29}{22} of the heaviest weight to the lightest, since the product of the number of weights and the average weight of the weights must be equal for the both scales, when equilibrium is attained. Since the numbers of the weights left are no more than 44, the smallest possible value for rr is, if not equal to 11, 43\frac{4}{3}. Since 43>2922\frac{4}{3} > \frac{29}{22}, we conclude that r=1r = 1, which means that if equilibrium is achieved, then there must be a same number of weights left on both scales.
Since the value of each weight on the left scale is even, the total weight on each of the scales when equilibrium is achieved must be even. Since the value of each weight on the right scale is odd, the number of weights on each scale must be a same even number; in fact, we can see that both scales must have 22 weights when equilibrium occurs. We can check easily that the following 66 cases are the only possibilities:
22+26=23+25,22+28=23+27,24+26=23+27,24+28=23+29,24+28=25+27,26+28=25+29. \begin{aligned} 22 + 26 &= 23 + 25, & 22 + 28 &= 23 + 27, & 24 + 26 &= 23 + 27, \\ 24 + 28 &= 23 + 29, & 24 + 28 &= 25 + 27, & 26 + 28 &= 25 + 29. \end{aligned}
For each of these 66 possibilities there are 22 occasions before equilibrium is achieved and 22 occasions after it is achieved, when you can make a choice of deciding which of the two remaining weights to remove from the scales, and therefore, the total number of ways of removing weights to attain equilibrium with some weights still remaining on the scales is 6×24=966 \times 2^4 = 96 and the desired answer to the problem is 57696=480576 - 96 = 480.

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.