In each cell of a table with $m$ rows and $n$ columns, where $m<n$, we put a non-negative real number such that each column contains at least one positive number. Show that there is a cell with a positive number such that the sum of the numbers in its row is larger than the sum of the numbers in its column.
Problem
Source: Bundeswettbewerb Mathematik 2020, Round 2 - Problem 4
Tags: combinatorics, inequalities, nonnegative, Sum
18.11.2020 09:08
https://dgrozev.wordpress.com/2020/09/02/numbers-in-a-table/
18.11.2020 11:17
.
19.11.2020 12:17
dgrozev wrote: https://dgrozev.wordpress.com/2020/09/02/numbers-in-a-table/ Elegant solution. Would you give me some motivation how did you come up with terms $a_{ij}$,$b_{ij}$?
19.11.2020 13:21
roughlife wrote: Elegant solution. It's the trademark of @dgrozev
19.11.2020 18:27
Thanks to all of you! Sometimes it happens, most of the time it doesn't. On the question about motivation. I have seen a special case of this problem when all the numbers are $1$'s. I think it was here, in this forum, and I even gave a similar solution. Unfortunately, I cannot find it. So, let's consider the case when all $a_{ij}$ are $1$'s. Imagine the corresponding matrix being the incidence matrix of a bipartite graph $G(A,B), |A|=m,|B|=n, m<n$. We should prove there exists an edge $e=ab$ with $\deg(a)>\deg(b)$. The beauty of the problem is that this fact is so obvious, but somehow elusive to prove. One way to make it is to seek contradiction by assuming $d(a)\le d(b)$ for any edge $e=ab$. Summing up these inequalities through all edges yields: $$\sum_{ab\in E(G)} d(a)\leq \sum_{ab\in E(G)} d(b)\quad (1)$$where we sum over all edges $ab, a\in A,b\in B$. It implies $$\sum_{a\in A} d(a)^2\leq \sum_{b\in B} d(b)^2\quad (2)$$What we know is $$\sum_{a\in A} d(a)= \sum_{b\in B} d(b)$$and $|A|<|B|$. Unfortunately, it's impossible to get contradiction from here. But look at the inequalities $(1)$ and $(2)$. If we put the terms $d(a),d(b)$ in $(1)$, as it is now, we get $(2)$. What should we put instead of these terms in order to get something that is more manageable than $(2)$. Ok, let's try with their reciprocals $1/d(a)$ resp. $1/d(b)$. Once again. We assume the statement is not true. Then $\frac{1}{d(a)}\geq \frac{1}{d(b)}$ for all edges $e=ab,a\in A,b\in B$. Summing up over the edges it yields $$\sum_{ab\in E(G)} \frac{1}{d(a)}\geq \sum_{ab\in E(G)} \frac{1}{d(b)}$$which implies $$\sum_{a\in A}1 \geq \sum_{b\in B}1$$or simply $|A|\ge |B|$. The last one is of course contradiction. Assigning those numbers, etc., as I did, is just a presentation trick. So, having in mind how to deal with this special case, it costs some tries to calibrate the things in the same spirit to work for any positive numbers.
13.09.2024 22:55
We uploaded our solution https://calimath.org/pdf/BWM2020-2-4.pdf on youtube https://youtu.be/lG7W7i4QEeE.