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
dgrozev
18.11.2020 09:08
https://dgrozev.wordpress.com/2020/09/02/numbers-in-a-table/
Tintarn
18.11.2020 11:17
For the sake of contradiction, assume that $(m,n)$ is a counterexample with minimal $n$.
This means that any smaller number of $k<n$ columns must have positive entries in at least $k$ rows, otherwise we could apply the hypothesis to this set of rows and columns, finding one row sum which is larger than the corresponding column sum, and noting that in the big table the row sums can only be larger, but the column sums remain the same.
In particular we must have $m=n-1$.
Now by Hall's Marriage Theorem, we can find a bijection between the first $n-1$ columns and the $n-1$ rows such that at the intersection, there are always positive entries (so the idea of using a bipartite graph actually turns out to be useful!).
W.l.o.g. the $i$-th row is paired with the $i$-th column.
Hence if $S_i$ and $Z_i$ are the sums of the $i$-th column and row, respectively, we have $S_i \ge Z_i$ and hence
\[S_1+\dots+S_{n-1} \ge Z_1+\dots+Z_{n-1}=S_1+\dots+S_n\]so that $S_n=0$ which is a contradiction to there being a positive entry also in the $n$-th column.
.
roughlife
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}$?
oty
19.11.2020 13:21
roughlife wrote: Elegant solution. It's the trademark of @dgrozev
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.
Cali.Math
13.09.2024 22:55
We uploaded our solution https://calimath.org/pdf/BWM2020-2-4.pdf on youtube https://youtu.be/lG7W7i4QEeE.