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
Problem
Source: 2020 Taiwan TST Round 3 Mock Exam P2
Tags: combinatorics, Taiwan
23.05.2020 08:34
The original version is: Find the least positive reals $k$ instead of 2.020 such that the statement is still true.
23.05.2020 17:05
But when the $N=5$ and the weights are $1, 6, 7, 8$ and $9$, "merge the two lightest monster" process has 2 dangerous mergences while $(1+6), 7, 8, 9 \to (7+9), 7, 8\to (7+8), 16 \to (15+16)$ have just 1 dangerous mergence. Did I misunderstand the problem?
24.05.2020 03:40
Hmm merging the two lightest monsters has dangerous level 1 instead of 2
24.05.2020 04:13
ltf0501 wrote: The original version is: Find the least positive reals $k$ instead of 2.020 such that the statement is still true. Slight modification to prevent confusion: Find the least positive real $k$ such that the statement holds for $x$ in place of $2.020$ for all real $x>k.$
29.05.2020 00:02
Edit: Oops, construction is not a counterexample for $k < 2$ as pointed out by the below.
29.05.2020 20:38
(Edited) Wait why is your solution correct? I think the proposed algorithm produces dangerous level $1$, only at the very first merge.
29.05.2020 20:48
Pathological wrote: We assume that $N > 3$, as otherwise the problem is lame. Consider a sequence of real numbers with $a_1 = 1, a_2 = 2 - \varepsilon, a_3 = 2,$ and $a_4 = 4 - 2 \varepsilon$ for some $\varepsilon>0$ to be chosen later. Define each subsequent $a_i$ to be the sum of the previous ones. If we let $\varepsilon < \epsilon^{10^{10^{10}}},$ then it's clear that applying the strategy of "merge the two lightest subsets of monsters" obtains a dangerous level of $2.$ However, it's not hard to see how to obtain a dangerous level of only $1.$ Start by merging $a_2$ and $a_3$, merging the result with $a_4$, and then merging the result with $a_1$ (the only dangerous merging). Afterwards, we can merge the two lightest subsets. $\square$ Why merging the two lightest monsters obtains dangerous level of $2$?? I think the merging process should be $$ (1, 2 - \epsilon, 2, 4 - 2\epsilon) \rightarrow (3 - \epsilon, 2, 4 - 2\epsilon ) \rightarrow (5 - \epsilon, 4 - 2\epsilon) \rightarrow 9 - 3\epsilon, $$which contains only 1 dangerous merging process(the first one).
29.05.2020 21:14
In my opinion, this problem is not easy at all. I just found a construction a few minutes ago.
30.05.2020 12:12
Here is a Codeforces problem with essentially the same setting: https://codeforces.com/contest/1098/problem/D.
19.06.2020 11:42
We will prove that the result using induction independent of the danger threshold. If $N=2$ there is only one strategy to merge the $2$ lightest monsters so merge the $2$ lightest is the best strategy for $N=2. $ Assume that is the best strategy forall $n\ge 2$ and strictly $<N . $ We will prove that merge the $2$ lightest is also the best strategy for $N. $ Let $\mathcal D $ be the danger threshold $(2.020) $ We obtain the $2$ cases Case 1- The mass of the lightest monster is more than $\frac {1}{\mathcal {D}} $ times the mass of the second lightest monster. Case 2- The mass of the lightest monster is $<\frac {1}{\mathcal {D}}$ times the mass of the second lightest monster. In case 1 merging the lightest two monsters is not dangerous. Therefore, perform this merge without increasing the dangerous level. This leaves us with with $N-1$ remaining monsters for which, by assuming merge the $2$ lightest is the best strategy. For case 1 merge the two lightest works for $N. $ In case 2 merging the $2$ lightest monsters is dangerous. Since all other monsters are at least as massive as the second lightest monster. Because merges only make more massive monsters, no matter when the lightest monster is merged, the merge will be dangerous. Perform this merge first between the lightest and second lightest monsters. This increases the dangerous level by one, that increase would have happened. We are again left with $N-1$ monsters for which, assume merge the $2$ lightest is the best strategy. In case 2, merge the $2$ lightest works for $N. $ Since, in both cases merge the $2$ lightest is the best strategy for $N $ given it is best strategy for $n <N. $ Also it is the best strategy for $N=2. $ By induction we conclude that for $N\ge 2, $ merge the $2$ lightest will always give the minimum dangerous level.
20.04.2021 18:26
@above I doubt your solution is correct and here is why: You never used the fact that the danger constant is $\geq 2$. If the constant is $<2$ there are several counterexamples. Take, for example, $\varepsilon\text{ and }\delta\to 0$ and let the danger constant be $3 / (2+\varepsilon)-\delta$. Take the numbers $\{1,2,2+\varepsilon,4+2\varepsilon\}$ Using the algorithm in the statement, we have \[\{1,2,2+\varepsilon,4+2\varepsilon\}\to\{3,2+\varepsilon,4+2\varepsilon\}\to\{5+\varepsilon,4+2\varepsilon\}\to\{9+3\varepsilon\}\]and observe that the first two mergences are dangerous because $2>3 / (2+\varepsilon)-\delta$ and $3 / (2+\varepsilon)>3 / (2+\varepsilon)-\delta$. Therefore, the danger level of this sequence is (at least) equal to $2$. But take a look at this sequnce of transformations \[\{1,2,2+\varepsilon,4+2\varepsilon\}\to\{1,4+\varepsilon,4+2\varepsilon\}\to\{1,8+3\varepsilon\}\to\{9+3\varepsilon\}.\]The latter sequence has a danger level of $1$, because $(2+\varepsilon) / 2<3 / (2+\varepsilon)-\delta$ and $(4+2\varepsilon) / (4+\varepsilon)<3 / (2+\varepsilon)-\delta$ as $\varepsilon\text{ and }\delta\to 0$.
28.10.2021 10:25
Whitewizard314 wrote: But when the $N=5$ and the weights are $1, 6, 7, 8$ and $9$, "merge the two lightest monster" process has 2 dangerous mergences while $(1+6), 7, 8, 9 \to (7+9), 7, 8\to (7+8), 16 \to (15+16)$ have just 1 dangerous mergence. Did I misunderstand the problem? no, the “merge the two lightest monsters” actually has one single dangerous mergence. $(1+6), 7, 8, 9 (dangerous) \to (7+7),9, 8 \to (9+8), 14 \to (17+14).$
28.10.2021 19:18
This post is made with the massive help of my good friend who converted my terrible handwriting into latex lmao For the sake of simplicity, I am going to use lowercase $n$ for the number of monsters. Call the algorithm of selecting the $2$ lightest monsters to merge the "funny" algorithm. I will show that the funny algorithm always works. Denote by $d = 2.02$ Claim: The funny algorithm will make a dangerous mergence if and only if there exists an integer $k \in (2,...,n)$ such that \[ m_1 + m_2 + ... + m_{k-1} < \frac{1}{d} \cdot m_k. \]Proof: Say the funny algorithm merges 2 monsters of weights $x \leq y$, say at step $t$, then we split this into $2$ cases. \[ \text{Case 1:} \; t = 1 \]This means $x = m_1$ and $y = m_2$, which is obvious. \[ \text{Case 2:} \; t \geq 2 \]It is obvious that with the funny algorithm, the weight of the lightest monster is a monovariant. Therefore, letting $x_i$, $y_i$ for $i = 1$ to $t$ be the weights of monsters merged on step $i$, with $x_i \leq y_i$, we have \[ x_i \leq y_i \leq x_{i+1} \; \text{for all} \; 1 \leq i \leq t-1 \rightarrow x_{t-1} \leq y_{t-1} \leq x_{t} < y_{t}. \] As the danger threshold is $2.02$, we know $y > 2x$. This implies that $x_{t-1} + y_{t-1} = x_t = x$, and that $x_i + y_i < y$ for all $1 \leq i \leq t - 1$. Moreover it reveals that the monsters with weight $y$ or above at step $t$ are actually at their initial size since step 1 and aren't a product of any mergence. This gives us the fact that the monster of weight $x$ at step $t$ is actually the product of every monster in step 1 with weight less than $y$, merged. This brings us to the conclusion that \begin{align*} y &= m_{t+1} \\ x &= m_1 + m_2 + ... + m_t \\ m_1 + m_2 + ... + m_t &< \frac{1}{d} \cdot m_{t+1} \end{align*}The forward proof is straightforward. Divide $S$ into $2$ groups, $S_1$ and $S_2$ where $S_1$ contains monsters of weight less than $m_k$, and $S_2$ containing the rest. By the condition of the claim, the funny algorithm will only merge monsters in group 1, and they will still have a weight less than $\frac{1}{d} \cdot m_k$ due to the condition of the claim again. This will force a dangerous mergence on step $k - 1$ on 2 monsters with weights $m_1 + m_2 + ... + m_{k-1}$ and $m_k$ respectively. From this we can conclude that the funny algorithm will only make a dangerous mergence on step $k$ if and only if \[ m_1 + m_2 + ... + m_k < \frac{1}{d} \cdot m_{k+1} \] On our final step we prove it by induction. Assume that a certain algorithm reduces the dangerous level to less than that of the funny algorithm for some $n \in \mathbb{N}$, and assume that it doesn't exist for any smaller values of $n$. For one, it is obvious that $n = 2$ obeys the problem statement. Now, onto the inductive step. Let $M_x < M_y$ be the weights of all monsters merged in step 1. We can assume that the rest of the steps follow the funny algorithm. From (1) it can easily be inferred that any dangerous mergence involving a monster at a step $k \in \mathbb{N}$ if $k + 1 \neq x$ and $k + 1 \neq y$, in the funny algorithm that starts from step 1 will occur in the algorithm that we claimed to work better as well. And, if $k = x$ and a dangerous mergence occurs in step $k-1$ in the funny algorithm starting at step 1, it would occur in the claimed optimal algorithm with a monster with weight $M_x + M_y$ as the larger one. In a similar manner, if $k = y$, the mergence of $M_x, M_y$ would be dangerous in itself, proving the claimed algorithm to not be any better than the funny algorithm, and so I'm done. $\blacksquare$
23.11.2022 22:01
I feel like the idea for solving this problem is not that hard, but writing it up has been painful... Order the monsters according to their weight $m_1\leq m_2\leq \cdots m_N$, and call monster number $k$ a threat if $$m_k>2.020(m_1+\cdots m_{k-1}).$$In particular, note that $m_1$ is never a threat. Consider a sequence of mergings $A$. Define an auxiliary counter $D_n(A)$ to be the number of dangerous mergings that have occurred after $n$ steps of $A$, and define the threat counter $T_n(A)$ to count the number of monsters that are threats after $n$ mergings of $A$. The quantity $T_n(A)+D_n(A)$ is the danger counter. ($0\leq n\leq N-1$). Notice how, at the end, the danger counter will be equal to the danger level . We recognize the following monovariant. Main claim: When merging two monsters, $T_n(A)+D_n(A)$ cannot decrease. By toying around it is easy to convince yourself that this is true; the proof, however, seems to require some attention to detail. To facilitate legibility, I prove this at the end of my post. Now, following up the main claim with the following lemma will solve the problem: Lemma: When $A$ consists of repeatedly merging the smallest two monsters (call this algorithm $B$) the quantity $T_n(A)+D_n(A)$ remains constant. Pf: At a given moment, suppose our set of monsters is $m_1\leq m_2\leq\dots$. After merging, clearly the former threats remain threats, with the exception of $m_2$ ($m_1$ is never a threat!). The main observation is that the new monster with weight $m_1+m_2$ cannot be a threat. To prove this, we consider two cases. If there is no monster (with weight $m$) satisfying $m_2\leq m\leq m_1+m_2$, then $m_1+m_2$ will be the smallest monster after the merge, and of course won't be a threat. Else, if $m_1+m_2$ were a threat, we must have $$2m=m+m>m_1+m_2\geq 2.020 m,$$which is a contradiction (this is where we use that $2.020>2$ !). Consequently, if monster $2$ is not a threat then both the auxiliary counter and the threat counter stay the same. If monster $2$ is indeed a threat, then the auxiliray counter will increase by one, but the threat counter will decrease by one. In both cases $T_n(A)+D_n(A)$ remains constant. $\blacksquare$ Finally then, since $D_{N-1}(A)$ is the danger level which we wish to minimize, and we have found that $$D_{N-1}(A)=T_{N-1}(A)+D_{N-1}(A)\geq T_0(A)+D_0(A)=T_0(A),$$the fact that this holds with equality when $A=B$ finnishes our solution. $\square$ Pf of the main claim: Essentially this has the same ideas as the proof of our lemma. Suppose we merge $m_i$ and $m_j$ (WLOG $i<j$). Let $k$ be the maximal index such that $m_k<m_i+m_j$ and consider the (possibly empty) sets $$ I_1=\{1, 2, \dots, i-1\}, I_2=\{i+1, \dots, j-1\}, I_3=\{j+1 \dots, k\}, I_4=\{k+1, \dots, N\}$$It is easy to see that the danger in each of these sets is clearly non decreasing, and the number of threats in each of $I_1$ and $I_4$ is invariant. We must prove that, if some of monster $i$ or monster $j$ are threats, then some new monsters become threats to counterbalance the loss in $T_n$. If monster $j$ is a threat, then the merge of monster $i$ and monster $j$ is dangerous, so $D_n$ increases by one. We now show that, in this case, $D_n$ would also increase by one. Consider two cases depending on $I_3$. Suppose that $I_3$ is non empty. I claim that before the merge, no $m_i$ with $i\in I_3$ was dangerous. Indeed, assuming the contrary, we could find an index $l$ such that $$m_{i}+m_j>m_l>2020 (m_1+\cdots +m_{l-1}), $$a contradiction. Thus, if monster $j$ is a threat, it is clear that after our merge, monster $j+1$ would become a threat, increasing the $T_n$ by one. Else, if $I_3$ is empty, it is clear that after the merge, the new monster with weight $m_i+m_j$ would be a threat. Hence, even if monster $i$ were a threat, the danger counter could not increase. Now, we must consider the case where $i$ is a threat and $j$ is not. If the merge is dangerous, we are done, so assume that $m_j<2.020m_i$. Again, differentiate in two cases, now according to the nature of $I_2$. If $I_2$ is not empty, the I claim that monster $i+1$ is not a threat. If it were, we would have $$m_{i+1}>2.020(m_1+\cdots +m_i)>2.020m_i>m_j,$$a contradiction to $j<i$. Hence, after the merge $i+1$ would become a threat, and we are done Else we consider when $i, j$ to be consecutive. In this case, $\min(a_{j+1}, a_i+a_j)$ becomes a threat, and we are again done. $\blacksquare$
27.07.2023 21:57
We solve the version given in the actual post. Let $c=2.020>2$ and suppose the weights of the monsters are $a_1 \leq \cdots \leq a_N$. The pith of the problem is the following claim: Claim: There must be at least as many dangerous merges as indices $i$ such that $a_i \geq c(a_1+\cdots+a_{i-1})$ (so monster $1$ is never a threat). Proof: Call both the indices $i$ described above, as well as the corresponding monsters "scary". We prove the claim by induction on the number of monsters, with base cases trivial. Suppose we merge monsters $i<j$ first. We would like to show that there are at least as many scary indices in the post-merge weights than the pre-merge weights if merging $i$ and $j$ isn't dangerous, and at most one less scary index in the post-merge weights otherwise. This is by casework. First, it is easy to see that any scary monster pre-merge, other than $i$ and $j$, remains scary post-merge, except for the second-lightest monster pre-merge if $i=1$, since the sum of the monsters that weigh less than any given monster other than $i$ and $j$ can never increase when $i$ and $j$ are merged. We will handle the $i=1$ edge case last; here assume that $i>1$, so if neither $i$ nor $j$ are scary pre-merge, then we are immediately done, so suppose otherwise. We first complete the case where $a_i<a_j$. If $j$ is scary pre-merge, then the merge is necessarily dangerous, since $ca_i<a_j$. If $a_i+a_j\leq a_{j+1}$, then the newly formed monster is still scary. If $a_i+a_j>a_{j+1}$, then monster $j+1$ could not have been scary pre-merge, but it is clearly scary post-merge, since monster $j$ was. Hence we can always find at least one newly scary monster, so we lose at most one scary monster, which is sufficient. Otherwise, $i$ is scary pre-merge, so $i+1$ is clearly scary post-merge and we're done, unless $i+1=j$ in which case "monster $i+1$" no longer exists. But in this case, if $a_i+a_j \leq a_{j+1}$, then the newly formed monster is scary, and otherwise $j+1$ could not have been scary pre-merge, and it is now clearly scary post-merge, so the number of scary monsters doesn't decrease. If $a_i=a_j$, then clearly $j$ is not scary, so $i$ should be. Then monster $i+1$ is still scary post-merge, unless $j=i+1$, in which case either $a_{j+1}$ is scary post-merge if $a_i+a_j>a_{j+1}$, or the newly formed monster is scary, so we are similarly done. Finally, suppose $i=1$. If $j$ is scary, then the merge must be dangerous, and either the previously non-scary monster $j+1$ becomes scary, or the newly formed monster is scary. This is enough to cover for the potential loss of monster $2$'s scaryness. Otherwise, since $i$ is clearly not scary, we only have to worry about the loss of monster $2$'s scaryness, but if monster $2$ was scary before, then the merge is dangerous as well, which covers for this. Therefore, we are also done. $\blacksquare$ The following claim will finish the problem. Claim: If we merge $a_1$ and $a_2$ and repeat (reassigning indices), then the number of dangerous merges will be exactly the same as the number of scary indices (among our initial monsters). Proof: We will show this by induction again, with base case of $N=2$ trivial. The goal is to prove that if this first merge isn't dangerous, then the number of scary monsters won't increase, and otherwise it will decrease by at least one. If merging monsters $1$ and $2$ is not dangerous, then monster $2$ cannot have been scary. Any pre-merge monster whose weight was at least $a_1+a_2$ is totally unaffected in terms of scaryness. On the other hand, if a pre-merge monster (other than $1$ and $2$) has weight at most $a_1+a_2$, it clearly cannot have been scary before. Finally, the newly formed monster cannot be scary either: if it is still the lightest monster, this is obvious. Otherwise, there must exist some monster with weight at least $a_2$ but at most $a_1+a_2$, so we have $a_1+a_2>ca_2$, which is absurd since $c>2$. Therefore, the number of scary monsters doesn't increase in this case. Otherwise, if merging monsters $1$ and $2$ is dangerous, then monster $2$ must have been scary. By the same reasoning, no pre-merge monster with weight at least $a_1+a_2$ could have been affected, no pre-merge monster with weight at most $a_1+a_2$ could have been affected, and the newly created monster cannot be scary either, hence the number of scary monsters must decrease by at least $1$, since we lose scary monster $2$. $\blacksquare$ The second claim implies that merging the two lightest monsters achieves equality in the lower bound established for the number of dangerous merges in the first claim, hence we are done. $\blacksquare$
04.02.2024 14:12
For the sake of convenience, let $c=2.020$. Let $a_1 \leq a_2 \leq \dots \leq a_N$ be the weights of the monsters. We begin by investigating the danger level acquired by always merging the two lightest monsters. In particular, we claim that the danger level acquired by merging the two lightest monsters is equal to the number of indices $1 < k \leq N$ such that $\sum\limits_{i=1}^{k-1}a_i < ca_k$. Call the monsters satisfying this condition "hazardous". Assume for now, that we always merge the two lightest monsters. Suppose that merging monsters $1$ and $2$ where $2$ is heavier than $1$ produces a monster $A$, heavier than the third lightest monster. We claim that continuing the sequence, there are no dangerous mergences until we merge $A$ with some other monster. Indeed, if there is a dangerous mergence while $A$ is still among the monsters, the lighter monster of the two is heavier than $2$. Which implies that the heavier monster of the two is heavier than $A$. Hence, the lighter monster has to be $A$. This implies that whenever merging two monsters $1$ and $2$ is dangerous, all of the monsters except $1$ have not been merged yet. Hence, there exists a positive integer $s$ such that $1$'s weight is equal to $\sum\limits_{i=0}^sa_i \implies \sum\limits_{i=0}^sa_i < ca_{s+1}$. $(1)$ It is clear that for any positive integer $1 < s \leq N$ satisfying $\sum\limits_{i=0}^{s-1} < ca_{s}$, the $s-1$'th mergence has to be dangerous. Paired with $(1)$, this implies our claim. Now, we are left to show that we can't do better. To do this, we simply induct on $N$. The base case $N=2$ is trivial. Suppose that the statement holds for $N-1$. It is clear that whenever we merge two non-hazardous monsters, the number of hazardous monsters stays the same. Hence, we are done by induction. Similarly, whenever we merge a hazardous monster with a non-hazardous monster, the mergence is dangerous, and the number of hazardous monsters decreases by at most one, so we are done by induction. Finally, if we merge two hazardous monsters $1$ and $2$ where $2$ is heavier than $1$, and the resulting monster is heavier than at least one of the monsters that are heavier than $2$, then the lightest one of these monsters (which couldn't have been hazardous before) will now be hazardous. Hence, the number of hazardous monsters will decrease by at most one. Otherwise, the resulting monster is obviously hazardous. Similarly, this implies that number of hazardous monsters also decreases by at most one. Then, we are done by induction. $\blacksquare$ Remark: Hazard orz.