Maths Olympiad Prep

Library / /2 of 6

, 2020

Combinatorics Difficulty 8.3 Shortlist Prove it Taiwan

There are NN monsters, each with a positive weight. On each step, two of the monsters are merged into one, whose weight is the sum of weights for the two original monsters. At the end, all monsters will be merged into one giant monster. During this process, if at any mergence, one of the two monsters has a weight greater than 2.020 times the other monster's weight, we will call this mergence dangerous. The dangerous level of a sequence of mergences is the number of dangerous mergence throughout its process. Prove that, no matter how the weights being distributed among the monsters, “for every step, merge the lightest two monsters” is always one of the merging sequences that obtains the minimum possible dangerous level.

Solution

The 2.020 in the original problem can be changed to any k>2k > 2, so we will prove the general statement for kk below.
Let us label the monsters so that the weight xix_i of the ii-th monster satisfies x1x2xNx_1 \le x_2 \le \dots \le x_N. We define a monster ii to be dangerous if and only if xi>kj<ixjx_i > k \sum_{j<i} x_j.
First, note that the initial number of dangerous monsters is a lower bound for the dangerous level. Suppose xix_i is dangerous, and let M={i1}M = \{i-1\}. Whenever monster number i1i-1 merges with monster number jj, add jj to the set MM. Then it is easy to see that in this process, the first time M{j:ji}M \cap \{j: j \ge i\} becomes nonempty, that mergence must be a dangerous mergence. This proves that the dangerous level is at least as large as the number of initially dangerous monsters.

Next, we prove that merging the lightest two monsters each time achieves this lower bound. Let us merge x1x_1 and x2x_2; this step is dangerous if and only if x2x_2 is dangerous. Next, let us consider the danger status of the N1N-1 monsters after the merge. Note that the danger status of a monster with weight greater than x1+x2x_1 + x_2 does not change before and after the merge, so we only need to consider monsters with weight x1+x2\ge x_1 + x_2; note that these monsters were not dangerous before the first two monsters were merged. Let one of these monsters have weight yy, with yx1+x2y \le x_1 + x_2.
- If yy is the lightest after the merge, then it must not be dangerous after the merge.
- If yy is not the lightest after the merge, then by the initial ordering of weights, the lightest monster after the merge has weight at least x2x_2, and hence kx2>2x2x1+x2ykx_2 > 2x_2 \ge x_1 + x_2 \ge y, so yy is also not dangerous.
The above two points together also prove that the merged weight x1+x2x_1 + x_2 is not dangerous either.

Combining the above, when we merge the lightest two monsters, if x2x_2 is not dangerous, then this mergence is not dangerous, and the number of dangerous monsters among the new N1N-1 monsters is the same as before. Conversely, if x2x_2 is dangerous, then this mergence is dangerous, and the number of dangerous monsters among the new N1N-1 monsters is the original number of dangerous monsters minus 1. Hence, by induction, this sequence achieves the lower bound of the dangerous level.

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 translated into English from zh; metadata (topic, difficulty) added by this project.