In every cell of a square table is a number. The sum of the largest two numbers in each row is $a$ and the sum of the largest two numbers in each column is b. Prove that $a = b$.
Problem
Source: Tournament of towns 2011
Tags: matrix, combinatorics
shinichiman
04.10.2016 16:31
Consider set $S$ of $2n$ numbers where each number is one of the two largest numbers in its row. Assume that among these numbers in $S$, $x_1$ numbers are in first column, ... , $x_n$ numbers are in last column then $x_1+x_2+\cdots+x_n=2n$. According to the assumption, consider first column, if we pick any two numbers from this column then its sum must less than $b$. Hence, if $A_1$ is the sum of numbers in first column then $A_1(x_1-1) \le \binom{x_1}{2} \cdot b$ or $A_1 \le \frac{x_1b}{2}$. Thus, $$an=\sum_{i=1}^nA_i \le \frac b2 \cdot \sum_{i=1}^nx_i= bn.$$Similarly, $bn \le an$ or $b \le a$. Thus, $a=b$.
math90
04.10.2016 20:12
But if $x_i=1$ for some $i$, your argument doesn't work.
Let $S$ be the set of $2n$ numbers where each number is one of the two largest numbers in its row.
Consider a bipartite graph $G$, whose vertices are the rows and the columns. The $i$th row and the $j$th column are connected if and only if $(i,j)\in S$.
Since $G$ contains $2n$ vertices and $2n$ edges, it contains a cycle, which is necessary even and contains at least $4$ vertices.
Hence there exist $2k$ vertices $x_1,x_2,\dots,x_{2k+1}=x_1$, where $k\geq 2$ and for all $1\leq i\leq k$, $x_{2i-1},x_{2i}$ are in the same row and $x_{2i},x_{2i+1}$ are in the same column (the indices are considered modulo $2k$). Thus
$ak=\sum_{i=1}^{k}(x_{2i-1}+x_{2i})=\sum_{i=1}^{2k}x_i=\sum_{i=1}^{k}(x_{2i}+x_{2i+1})\leq bk$
Thus $a\leq b$. Similarly $b\leq a$. Thus $a=b$.
SnowPanda
19.01.2022 10:30
Assume not, so WLOG $a < b$. Label the rows and columns $1$ through $n$. Draw a graph on $n$ vertices and for each column, draw an edge between the row numbers with the two greatest elements of that column (breaking ties arbitrarily) -- multiple edges between two vertices are allowed.
This graph has $n$ vertices and $n$ edges, so it must contain a cycle $(r_1r_2\cdots r_k)$, possibly of length $2$. Suppose edge $r_ir_{i + 1}$ corresponds to column $c_i$. Then if $x(r, c)$ denotes the entry in $(r, c)$, we have \[\sum x(r_i, c_i) + x(r_{i + 1}, c_i) = bn\]by looking at columns. But \[\sum x(r_i, c_{i - 1}) + x(r_i, c_i) \leq an\]by looking at rows (since each term is at most the sum of the two largest numbers in each row). But these are the same sum, so $bn \leq an$, contradiction as $a < b$.
[asy][asy]
unitsize(1cm);
DefaultHead.size=new real(pen p=currentpen) {return 2.5mm;};
for (int i = 0; i <= 5; ++i) {
draw((-0.5, i - 0.5)--(4.5, i - 0.5), gray);
draw((i - 0.5, -0.5)--(i - 0.5, 4.5), gray);
}
draw((0, 3)--(0, 2), heavycyan+linewidth(1.5), EndArrow);
draw((2, 2)--(2, 1), heavycyan+linewidth(1.5), EndArrow);
draw((4, 1)--(4, 4), heavycyan+linewidth(1.5), EndArrow);
draw((3, 4)--(3, 3), heavycyan+linewidth(1.5), EndArrow);
draw((0, 2)--(2, 2), heavyred+linewidth(1.5), EndArrow);
draw((2, 1)--(4, 1), heavyred+linewidth(1.5), EndArrow);
draw((4, 4)--(3, 4), heavyred+linewidth(1.5), EndArrow);
draw((3, 3)--(0, 3), heavyred+linewidth(1.5), EndArrow);
[/asy][/asy]
CANBANKAN
12.06.2022 21:46
Let $a_{i,j}$ be the number on the $i$th row (from the top) and $j$th column (from the left). Induct on $n$, with the base case $n=2$ holding because the sum of all entries of the square is $2a=2b$. Let $X$ be the largest entry in the box. Shift the rows and columns so that it is at the bottom left corner. Let $C$ be the assertion that there exists another column, call column $c\ne 1$ with one of the largest two numbers on the first row, and $R$ there exists another row $r\ne 1$ with one of the largest two numbers on the first column. Case 1: $C,R$ both holds. The sum of the two numbers in row 1 is at least $X+t$ where $t$ is on row 1 and column $c$. Thus, $a\ge X+t$. Since $t$ is one of the largest two in column $c$ and the other number is at most $X$, we get $b\le X+t\le a$. Similarly, $b\ge a$, so $b=a$. Case 2: $R$ doesn't hold. (If $C$ doesn't hold we are done by a symmetrical argument) Note $a_{1,t}$ is at most the second largest number of row $j$ for any $2\le t,j\le n$ because $a=a_{1,1}+a_{1,t}=X+a_{1,t} = a_{j,c_j}+a_{j,d_j}$ for some $c_j,d_j$. Since $X\ge \max\{a_{j,c_j},a_{j,d_j}\}$, $a_{1,t}\le \min\{a_{j,c_j},a_{j,d_j}\}$ Consider an alternate matrix $(b_{i,j})_{2\le i,j\le n}$. Initially, $b_{i,j}=a_{i,j}$. For each $t$ that satisfies $a_{1,t}$ is one of the two largest numbers in column $t$, say the two largest numbers are $a_{1,t}, a_{m,t}$. Select $2\le j\le n$ such that $j\ne m$, and reset $b_{j,t}$ to be $\max\{b_{j,t},a_{1,t}\}$. In column $t$, the two largest numbers in $(b_{i,j})$ is equal to $b$. Also, this operation doesn't change the two largest numbers in each row of the matrix $(b_{i,j})$, so the sum of the two largest in each row is $a$. We apply inductive hypothesis on $n-1$ and $b$ to get $a=b$, as needed.