Given $19$ red boxes and $200$ blue boxes filled with balls. None of which is empty. Suppose that every red boxes have a maximum of $200$ balls and every blue boxes have a maximum of $19$ balls. Suppose that the sum of all balls in the red boxes is less than the sum of all the balls in the blue boxes. Prove that there exists a subset of the red boxes and a subset of the blue boxes such that their sum is the same.
Problem
Source: INAMO 2019 P2
Tags: combinatorics, number theory
02.07.2019 22:42
This is the sketch of my proof: Replace $19$ with $m$ and replace $200$ with $n$, and the problem holds as long as $m \leq n$. That is, given $x_1, \dots, x_m \in [1,n]$ and $y_1, \dots, y_n \in [1,m]$ and $\sum x_i < \sum y_i$ then there exists a sub-sum of $x_i$ that is equal to a sub-sum of $y_i$. This is easy to show for $m=1$, or even $m=2$ (just do even/odd analysis). Now suppose $P(m,n)$ is the problem statement. WLOG we may assume that $x_1 \geq \dots \geq x_m, y_1 \geq \dots \geq y_n$. Also define $f(k) = |\{ i | x_i = k\}|, g(k) = |\{i | y_i = k\}$ If $y_1 < m$ (or in other words $g(m) = 0$ then just eliminate $x_1$. Then the remaining numbers satisfy the conditions of $P(m-1,n)$, so the required sub-sums exist. Now if $y_1 = m$, and there's a single $x_i$ that equals to $n$ (that is, $f(n) = 1$), then eliminate $y_1$, but in turn, also replace $x_1$ with $x_1' = x_1-m$. The remaining numbers satisfy the conditions of $P(m,n-1)$. If the sub-sums exist,it can be extended back to the old configuration by possibly adding the deleted $y_1$ appropriately. Meaning, if $x_1'$ is part of that new sub-sum, then in the old configuration $x_1$ would have been $x_1' + m$, so we can include $y_1 = m$ in the new sub-sum to balance it out. We can keep doing this one at a time until $g(m) = 0$, which then go back to the case above. Of course there is a problem if $f(n) > 1$ (there are multiple $x_i$s such that $x_i = n$). Suppose $f(n) = k$ (where $1 < k < m$), then replace $x_1, \dots, x_k$ with $x_1-y_1, \dots, x_k - y_k$, and also eliminate $y_1, \dots, y_k$ at the same time. Then the remaining numbers satisfy the conditions of $P(m, n-k)$. How do we know that $y_k \geq k$ (therefore justifying our claim that the new numbers satisfy $P(m,n-k)$? Because if not then $\sum x_i > \sum y_i$ which is a contradiction (use the fact that $f(n) = k$ and $y_k < k$ to get the contradiction). The point here is to keep reducing $g(m)$ one or $k$ at a time until it is zero, then we can eliminate $x_1$. The induction step is only on $m$.
03.07.2019 02:23
Here's a frendlier solution. Let the numbers be $a_1, a_2, a_3, \dots, a_{19}, b_1, b_2, \dots, b_{200}$. We know that $b_1 + b_2 + b_3 + \dots + b_{200} > a_1 + a_2 + \dots + a_{19}$. Let $f(k)$ be a function mapping $\{1, 2, \dots 19 \} \to \{ 1, 2, \dots, 200 \}$ such that it is the largest $n$ such that for every $k$ \[ b_1 + b_2 + \dots + b_{f(k)} \ge a_1 + a_2 + \dots + a_k \]If for some $k$, equality holds. Then we are hence finished. If not, notice that \[0 < g(k) = b_1 + b_2 + \dots + b_{f(k)} - (a_1 + a_2 + \dots + a_k) \le 18 \]For every $k \in \{ 1, 2, \dots, 19 \}$. By Pigeon Hole, there must be two $i$ and $j$ such that their value $g(k)$ is the same . Substract them, we are hence finished.
03.07.2019 15:55
Also see this problem from Putnam 1993
03.07.2019 22:31
Thank you for this observation