Problem 1102

The question is related to problem 2518 and exercise 2304. (Their solutions can be found in the January and May issues of 1986, respectively.) From the note added to the solution of the latter, it is clear that the "balancing procedure" applied in both cases does not necessarily lead to a result. That is, if we assign weights to the given numbers and place them in the pans of a two-pan balance in decreasing order of magnitude, placing them in the left pan if the balance is even, and otherwise in the lighter pan, the pans will not necessarily be in balance when the weights run out.

If the procedure "gets stuck," that is, placing a weight of mass $m$ in one of the pans would exceed half the total mass, 50 grams, then the total mass of the weights in both pans up to this point is at least $50-(m-1)=51-m$, so at most $2m-2$ mass of weights remain off the balance. The mass in the pans is at most $100-m$, and thus up to the point of getting stuck, we could have placed at most

$$\left[\frac{100-m}{m}\right]=\left[\frac{100}{m}\right]-1$$

weights on the balance, since each of the weights used so far is at least $m$ in mass due to the decreasing order.

Thus, we still need to place at least $35-\left(\left[\frac{100}{m}\right]-1\right)=36-\left[\frac{100}{m}\right] \geqq 36-\frac{100}{m}$ weights, and their total mass is at most $2m-2$ according to the first estimate derived from the fact of getting stuck. More precisely, excluding the "critical" weight of mass $m$, at least $35-\frac{100}{m}$ weights are left, each with a mass of at most $m-2$ grams.

Since the mass of each weight is at least 1, we have $35-\frac{100}{m} \leqq m-2$, or $m^2 - 37m + 100 \geqq 0$. Given that $m$ is an integer, this inequality holds if and only if $35 \leqq m$ or $2 \geqq m$.

The case $m \geqq 35$ is not possible, because in the decreasing order, there would already be at least one weight of at least 35 grams in each pan before getting stuck, and together with the "critical" weight of mass $m$, their total would be at least $3 \cdot 35$, which is greater than 100.

With a weight of mass $m=1$, the procedure cannot get stuck, as in this case, proceeding one by one, the 50-gram mass in either pan cannot be exceeded.

Thus, the procedure can only get stuck in the case $m=2$, which can happen if 49 grams of weight have accumulated in both pans, and a 2-gram weight remains. (In this case, we have no 1-gram weights.) This can indeed occur, for example, if we have 30 weights of 3 grams and 5 weights of 2 grams. It can be shown that in this case, there exists a subset of the weights in each pan such that the difference in their total mass is exactly 1 gram. By swapping these two subsets, the difference between the pans becomes 2, which can be balanced with the remaining weight. However, we will choose a different path now.

If there are no 1-gram weights, then the number of 2-gram weights is clearly at least five $(4 \cdot 2 + 31 \cdot 3 > 100)$. Let's set aside five of the 2-gram weights. We will show that among the remaining thirty weights, there exists a subset whose total mass is an even number between 40 and 50, and thus can be completed to 50 grams using the set-aside 2-gram weights.

The total mass (90 grams) and the number (30) of the remaining weights are both even, so the number of odd-mass and even-mass weights among them is also even. Therefore, we can pair the odd-mass weights and the even-mass weights separately and consider the sum of the weights in each pair. This way, we get 15 even numbers, each at least 4, and their total is 90. We will show that among these, there are some whose sum $S$ (which is clearly even) satisfies $40 \leqq S \leqq 50$.

Let the 15 numbers in decreasing order be $b_1, b_2, \ldots, b_{15}$, and let $S_k$ be the sum of the first $k$ numbers. Since $b_1 \geqq 4$, we have $S_k = 90 - (b_{k+1} + \ldots + b_{15}) \leqq 90 - (15-k) \cdot 4 = 30 + 4k$, so $S_5 \leqq 50$. If $S_5 \geqq 40$, we are done.

If $S_5 \leqq 38$, then $S_5 \geqq 5 \cdot b_5$ implies $b_5 \leqq \frac{38}{5} < 8$, so if $i \geqq 5$, then $b_i \leqq 6$. Therefore, if we start from a number less than 40 and increase it by at most 6 at each step until we reach 90, we cannot "skip" the interval [40, 50], so there will be some $k$ for which $40 \leqq S_k \leqq 50$. This completes the proof.