Return to Answer

Edit: Looks like "a few hours" plus "20 minutes" passed, but Yaakov is still unconvinced, so I'm adding the pair warm-up. I'll go from the back, the way I figured it myself.

1. If you have $m\ge 2$ numbers with sum $S$, then the maximal pair has the sum $\ge 2S/m$.

2. If you have several marked positions in the matrix so that each column that contains a marked position at all contains at least 2 of them, then the maximal column pair has the sum $\ge 2S/N$ where $S$ is the sum of all numbers in marked positions and $N$ is the number of marked positions.

3. Thus, if we mark all positions of two largest numbers in each row, and find a submatrix with $a$ rows such that each its row contains two marked positions and each its column contains at least 2, then we will have the maximal column sum at least $2a/(2a)=1$ because $a$ is the sum of marked entries in this submatrix and $2a$ is the number of entries (I again assume $R=1$.

4. It remains to find such a submatrix. To this end forget all initial numbers and put free variables in the marked positions and $0$ everywhere else. Then we have $2n$ free variables. Restrict them by the equations row sums=column sums=0 ($2n-1$ independent homogeneous equations). We have a non-trivial solution. Look at each row with a non-zero free variable in that solution. It must have another free variable $\ne 0$ too to balance the first one. Now look at the columns with at least one non-zero free variable and observe the same. Thus these rows and columns will give us the desired submatrix.

The case of triples is complicated by the fact that we have to use the extra $n$ free variables and $n$ equations in a somewhat inventive way. To have the analogue of 2) for triples (with $3S/N$), we would need one extra equation for each column and each row to avoid two-entry solutions (any non-trivial solution of $x_1+\dots+x_n=x_1+2x_2+\dots+nx_n=0$ has at least 3 non-zero entries), but that's too much (which isn't surprising because that would prove $C\ge 1$, which is false). So we try to enforce columns, but then we cannot guarantee all three entries in the rows, only 2. If the sum of any 2 of the 3 largest entries in the rows were $\ge 1/2$, i.e., if there were no entries $\ge 1/2$, that would be enough because if in the similarly chosen we had $b$ rows with 2 entries and $c$ rows with 3 entries, we would have $S\ge \frac 12 b+c$ and $N=2b+3c$, resulting in the bound $3\frac{\frac 12 b+c}{2 b+3c}\ge\frac 34$, as required. But we may have entries $\ge 1/2$, so we need to take special care of them. We do it by sacrificing one free variable in each row containing them, which forces us to sacrifice one equation too. Then the columns for which we don't have the additional equation would have to be augmented by a third element, which increases $N$ by their number (hence $N+a$ instead of $N$ in the denominator). The estimate of $S$, however, improves to $\frac 34a+\frac 12b+c$, and we can still manage.

I hope this warm-up facilitates reading a little bit. Apologies for extra misprints if I introduced them :-).

$3/4$ and $4/3$ are correct bounds. You can use the same linear algebra trick as for pairs but you should choose equations more carefully an there is some small casework.

Let $R=1$ (just not to write it as a factor every time). In each row in which the maximal entry is $\ge 1/2$ mark its position red and the position of the next largest entry black. Together they'll give you at least $3/4$. Note that if two of entries $\ge 1/2$ stand in one column, then we already have $C\ge 1$, so we may assume that red positions all stand in different columns. If the largest row entry is $<\frac 12$, mark the positions of 3 largest elements black. Now that in this case the sum of any 2 black numbers in the row is $\ge\frac 12$. Let $m$ be the number of red positions.

Now put free variables into all marked positions. We have $3n-m$ free variables. The equations we'll use are row sums=column sums=0 (there are only $2n-1$ equations here because the sum of all row sums equals the sum of all column sums) plus, for every column without a red entry, we require $x_1+2x_2+\dots+nx_n=0$. That adds $n-m$ equations and we are still fine with the existence of a non-trivial solution.

Now, as usual, take this solution and consider the positions with non-zero entries. Take the minimal rectangular submatrix containing all such positions. Notice that each row in it contains $\ge 2$ marked entries and if $a$ is the number of red entries in it, then all but $a$ columns have at least 3 marked entries and the remaining $a$ columns (those with a red entry) have at least 2. Thus, choosing some extra entry in those $a$ columns anywhere, we get a picture in which every column has at least 3 entries, so the maximal column triple sums up to $\ge 3S/(N+a)$ where $N$ is the number of marked entries in the unmodified submatrix. Now, $N=2a+2b+3c$ where $b$ is the number of rows in the submatrix with 2 black entries and $c$ is that with 3 black entries. On the other hand $S\ge \frac 34 a+\frac 12b+c$. It remains to note that $$ 3\frac{\frac 34 a+\frac 12b+c}{3a+2b+3c}\ge \frac 34 $$ for any non-negative $a,b,c$.

$3/4$ and $4/3$ are correct bounds. You can use the same linear algebra trick as for pairs but you should choose equations more carefully an there is some small casework.

Let $R=1$ (just not to write it as a factor every time). In each row in which the maximal entry is $\ge 1/2$ mark its position red and the position of the next largest entry black. Together they'll give you at least $3/4$. Note that if two of entries $\ge 1/2$ stand in one column, then we already have $C\ge 1$, so we may assume that red positions all stand in different columns. If the largest row entry is $<\frac 12$, mark the positions of 3 largest elements black. Now that in this case the sum of any 2 black numbers in the row is $\ge\frac 12$. Let $m$ be the number of red positions.

Now put free variables into all marked positions. We have $3n-m$ free variables. The equations we'll use are row sums=column sums=0 (there are only $2n-1$ equations here because the sum of all row sums equals the sum of all column sums) plus, for every column without a red entry, we require $x_1+2x_2+\dots+nx_n=0$. That adds $n-m$ equations and we are still fine with the existence of a non-trivial solution.

Now, as usual, take this solution and consider the positions with non-zero entries. Take the minimal rectangular submatrix containing all such positions. Notice that each row in it contains $\ge 2$ marked entries and if $a$ is the number of red entries in it, then all but $a$ columns have at least 3 marked entries and the remaining $a$ columns (those with a red entry) have at least 2. Thus, choosing some extra entry in those $a$ columns anywhere, we get a picture in which every column has at least 3 entries, so the maximal column triple sums up to $\ge 3S/(N+a)$ where $N$ is the number of marked entries in the unmodified submatrix and $S$ is the sum of all entries in the corresponding positions. Now, $N=2a+2b+3c$ where $b$ is the number of rows in the submatrix with 2 black entries and $c$ is that with 3 black entries. On the other hand $S\ge \frac 34 a+\frac 12b+c$. It remains to note that $$ 3\frac{\frac 34 a+\frac 12b+c}{3a+2b+3c}\ge \frac 34 $$ for any non-negative $a,b,c$.

$3/4$ and $4/3$ are correct bounds. You can use the same linear algebra trick as for pairs but you should choose equations more carefully an there is some small casework.

Let $R=1$ (just not to write it as a factor every time). In each row in which the maximal entry is $\ge 1/2$ mark its position red and the position of the next largest entry blue. Together they'll give you at least $3/4$. Note that if two of entries $\ge 12$ stand in one column, then we already have $C\ge 1$, so we may assume that red positions all stand in different columns. If the largest row entry is $<\frac 12$, mark the positions of 3 largest elements black. Now that in this case the sum of any 2 black numbers in the row is $\ge\frac 12$. Let $m$ be the number of red positions.

Now put free variables into all marked positions. We have $3n-a$ free variables. The equations we'll use are row sums=column sums=0 (there are only $2n-1$ equations here because the sum of all row sums equals the sum of all column sums) plus, for every column without a red entry, we require $x_1+2x_2+\dots+nx_n=0$. That adds $n-a$ equations and we are still fine with the existence of a non-trivial solution.

Now, as usual, take this solution and consider the positions with non-zero entries. Take the minimal rectangular submatrix containing all such positions. Notice that each row in it contains $\ge 2$ marked entries and if $a$ is the number of red entries in it, then all but $a$ columns have at least 3 marked entries and the remaining $a$ columns (those with a red entry) have at least 2. Thus, choosing some extra entry in those $a$ columns anywhere, we get a picture in which every column has at least 3 entries, so the maximal column triple sums up to $\ge 3S/(N+a)$ where $N$ is the number of marked entries in the unmodified submatrix. Now, $N=2a+2b+3c$ where $b$ is the number of rows in the submatrix with 2 black entries and $c$ is that with 3 black entries. On the other hand $S\ge \frac 34 a+\frac 12b+c$. It remains to note that $$ 3\frac{\frac 34 a+\frac 12b+c}{3a+2b+3c}\ge \frac 34 $$ for any non-negative $a,b,c$.

$3/4$ and $4/3$ are correct bounds. You can use the same linear algebra trick as for pairs but you should choose equations more carefully an there is some small casework.

Let $R=1$ (just not to write it as a factor every time). In each row in which the maximal entry is $\ge 1/2$ mark its position red and the position of the next largest entry black. Together they'll give you at least $3/4$. Note that if two of entries $\ge 1/2$ stand in one column, then we already have $C\ge 1$, so we may assume that red positions all stand in different columns. If the largest row entry is $<\frac 12$, mark the positions of 3 largest elements black. Now that in this case the sum of any 2 black numbers in the row is $\ge\frac 12$. Let $m$ be the number of red positions.

Now put free variables into all marked positions. We have $3n-m$ free variables. The equations we'll use are row sums=column sums=0 (there are only $2n-1$ equations here because the sum of all row sums equals the sum of all column sums) plus, for every column without a red entry, we require $x_1+2x_2+\dots+nx_n=0$. That adds $n-m$ equations and we are still fine with the existence of a non-trivial solution.

Now, as usual, take this solution and consider the positions with non-zero entries. Take the minimal rectangular submatrix containing all such positions. Notice that each row in it contains $\ge 2$ marked entries and if $a$ is the number of red entries in it, then all but $a$ columns have at least 3 marked entries and the remaining $a$ columns (those with a red entry) have at least 2. Thus, choosing some extra entry in those $a$ columns anywhere, we get a picture in which every column has at least 3 entries, so the maximal column triple sums up to $\ge 3S/(N+a)$ where $N$ is the number of marked entries in the unmodified submatrix. Now, $N=2a+2b+3c$ where $b$ is the number of rows in the submatrix with 2 black entries and $c$ is that with 3 black entries. On the other hand $S\ge \frac 34 a+\frac 12b+c$. It remains to note that $$ 3\frac{\frac 34 a+\frac 12b+c}{3a+2b+3c}\ge \frac 34 $$ for any non-negative $a,b,c$.