(a) A $2 \times n$-table (with $n > 2$) is filled with numbers so that the sums in all the columns are different. Prove that it is possible to permute the numbers in the table so that the sums in the columns would still be different and the sums in the rows would also be different. ($2$ points) (b) A $100 \times 100$-table is filled with numbers such that the sums in all the columns are different. Is it always possible to permute the numbers in the table so that the sums in the columns would still be different and the sums in the rows would also be different? ($6$ points)
Problem
Source: Tournament of Towns Spring 2015 Senior A-level
Tags: combinatorics
13.04.2017 07:07
Okay, this one is cute. (a): If the two row sums are already distinct, then we have nothing to care about; so suppose they are equal. If there is a column with two distinct numbers, then swapping them would fix the issue. Otherwise, say each column contains a pair of the same number. So the table looks like this:$$\begin{array}{|c|c|c|c}\hline a_1 & a_2 & a_3 & \quad \cdots\quad \\ \hline a_1 & a_2 & a_3 & \cdots \\ \hline \end{array}$$Suppose WLOG that $a_1,a_2,a_3$ are the biggest three elements. Since the column sums $2a_1,2a_2,\cdots ,2a_n$ are all distinct, we have that these $a_i$'s are all distinct. Consider a new, tweaked array:$$\begin{array}{|c|c|c|c}\hline a_1 & a_3 & a_3 & \quad \cdots\quad \\ \hline a_2 & a_2 & a_1 & \cdots \\ \hline \end{array}$$Note that the column sums are still different; because if we had, say $a_1+a_2=a_3+a_2$, then we'd get $a_1=a_3$, which is false. Also, we can't have, say, $a_1+a_2=a_i+a_i$ for some $i\not\in\{1,2,3\}$, because $a_1,a_2>a_i$. Now the row sums must have become distinct, or we'd have $a_1+a_3+a_3=a_2+a_2+a_1\implies a_2=a_3$, which is wrong. This finishes (a). $\blacksquare$ (b): We claim that such a permutation isn't always feasible. Before we get to the proof, we need a small lemma: Lemma: Suppose $n\ge 3$ is an integer. If $x_1,x_2,\cdots ,x_n$ are distinct nonegative integers satisfying $$x_1+x_2+\cdots +x_n=\frac{n^2-n+1}{2},$$then $(x_1,x_2,\cdots ,x_n)$ is $(0,1,2,\cdots ,n-3,n-2,n)$ upto permutation. Proof: We induct on $n$. The base case $n=3$ is obvious (and the $n=4$ case is well-known to Kakuro solvers); let's prove it for general $n>3$. If all of $x_i$'s were nonzero, then we'd have $$x_1+x_2+\cdots +x_n\ge 1+2+3+\cdots +n=\frac{n^2+n}{2}>\frac{n^2-n+2}{2}.$$Of course, this is bad. Therefore one of the $x_i$'s is $0$; suppose WLOG $x_1=0$. Then the $n-1$-tuple $(x_2-1,x_3-1,\cdots ,x_n-1)$ satisfies the conditions of the induction hypothesis, and this gets our job done. $\square$ Now for the main proof. Consider the $100\times 100$ array defined as follows: fill the second column with $1$ one, third column with $2$ ones, fourth column with $3$ ones, $\cdots$, $99-$th column with $98$ ones. The $100-$th column, is however, filled with $100$ ones. The remaining cells are all stuffed with zeros. Of course, the column sums are all different. Suppose there's a way to permute these $4951$ ones so that column sums are distinct and the row sums are distinct as well. Suppose $x_i$ is the number of ones in the $i-$th column and $y_i$ is the number of ones in the $i-$th row. Note that $x_1,\cdots ,x_{100}$ are distinct nonnegative integers summing to $4951=\tfrac{100^2-100+2}{2}$, so our lemma says that $(x_1,\cdots ,x_{100})$ is a permutation of $(0,1,\cdots , 98,100)$. Suppose $x_a=100$. In a similar manner, we see that $(y_1,\cdots ,y_{100})$ is a permutation of $(0,1,\cdots , 98,100)$; say $y_b=0$. Now the $a-$th column has all $100$ cells filled with ones, and $b-$th row has no one at all, so there's a Schrödinger's one at their intersection, which is not allowed in combinatorics. Done! $\blacksquare$