There are 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.
, 2020
Solution
The 2.020 in the original problem can be changed to any , so we will prove the general statement for below.
Let us label the monsters so that the weight of the -th monster satisfies . We define a monster to be dangerous if and only if .
First, note that the initial number of dangerous monsters is a lower bound for the dangerous level. Suppose is dangerous, and let . Whenever monster number merges with monster number , add to the set . Then it is easy to see that in this process, the first time 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 and ; this step is dangerous if and only if is dangerous. Next, let us consider the danger status of the monsters after the merge. Note that the danger status of a monster with weight greater than does not change before and after the merge, so we only need to consider monsters with weight ; note that these monsters were not dangerous before the first two monsters were merged. Let one of these monsters have weight , with .
- If is the lightest after the merge, then it must not be dangerous after the merge.
- If is not the lightest after the merge, then by the initial ordering of weights, the lightest monster after the merge has weight at least , and hence , so is also not dangerous.
The above two points together also prove that the merged weight is not dangerous either.
Combining the above, when we merge the lightest two monsters, if is not dangerous, then this mergence is not dangerous, and the number of dangerous monsters among the new monsters is the same as before. Conversely, if is dangerous, then this mergence is dangerous, and the number of dangerous monsters among the new monsters is the original number of dangerous monsters minus 1. Hence, by induction, this sequence achieves the lower bound of the dangerous level.