Problem

Source: 2020 Taiwan TST Round 3 Mock Exam P2

Tags: combinatorics, Taiwan



There are $N$ 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 obtain the minimum possible dangerous level. Proposed by houkai