It's possible to rearrange each column of a matrix to satisfy a certain condition. (APMC 1984)

Question

Let $A$ be an $m \times n$ array of real numbers, each with absolute value at most $1$. Suppose that the sum of elements of each column of $A$ equals zero. Show that we can rearrange the numbers in each column of $A$ so that the absolute value of the sum of the elements of each row of the rearranged array is smaller than $2$.

Source : Austrian-Polish Mathematical Competition 1984 Problem 7

Added question : Can the bound $2$ be lowered? If it can, what is the smallest possible value $t=t(m,n)$ such that we can arrange the numbers in each column so that the absolute value of the sum of the elements of each row of the rearranged array is smaller than or equal to $t$?

My attempt :

For $n=2$, the claim is almost trivial. Suppose that $x_1,x_2,...,x_m$ and $y_1,y_2,...,y_m$ be the numbers in the first and the second columns, resp. We may rearrange the numbers so that $x_1\ge x_2 \ge ... \ge x_m$ and $y_1\le y_2 \le ... \le y_m$.

Suppose $x_k\ge 0>x_{k+1}$ and $y_{l}\le 0<y_{l+1}$. If $k=l$, then $$|x_i+y_i|\le \max\{|x_i|,|y_i|\}\le 1<2$$ for all $i=1,2,..,m$. If $k<l$, then $x_{k+1}+y_{k+1},x_{k+2}+y_{k+2},...,x_l+y_l$ is negative. Any of the $l-k$ numbers can have absolute value $\ge 2$ only when it equals $-2$. In this case there exists $j\in\{k+1,k+2,...,l\}$ st $x_j=-1$ and $y_j=-1$. So $x_j=x_{j+1}=...=x_{m}=-1$ and $y_1=y_2=...=y_j=-1$.

Because $x_1+x_2+...+x_m=0$, we have $x_1+x_2+...+x_{j-1}=m-j+1$. Similarly, $y_{j+1}+y_{j+2}+...+y_{m}=j$. So: $$j-1 \ge |x_1+x_2+...+x_{j-1}| =m-j+1$$ and $$m-j \ge |y_{j+1}+y_{j+2}+...+y_m| =j.$$ That is, $m+2\le 2j \le m$. This is a contradiction. So, all $x_{k+1}+y_{k+1},x_{k+2}+y_{k+2},...,x_l+y_l$ have absolute values $<2$. Other sums $x_i+y_i$ for $i=1,2,...,k,l+1,l+2,...,m$ obviously have absolute values $<2$. We are done.

Similarly if $k>l$, we have the same conclusion.

Answer 1

A "great contender" for consideration is the permutation that minimizes the sum of the absolute value of the sum of each rows.
As it turns out, this works, and you just have to check the algebra.

Claim: For a given permutation of the columns, let the sum of the rows be $s_1, s_2, \ldots s_m$. The permutation $S$ that minimizes $ \sum |s_i|$ will also satisfy $|s_i | < 2$.

Proof by contradiction: Suppose not. WLOG $s_1 \geq 2$.
Since $ \sum s_i = 0$, WLOG $s_2 < 0$.
The idea here is that we want to reduce positive $s_1$ and increase negative $s_2$, and hope that the sum decreases.
$s_1 = \sum b_{1i} \geq 2 > 0$, $s_2 = \sum b_{2i} < 0$.
So there exists a $k$ such that $b_{1k} > b_{2k}$, which we can use to make the switch.
Observe that $ b_{1k} - b_{2k} \leq 1 - (-1) = 2$.

Consider the permutation $S'$ that in addition switches $b_{1k}, b_{2k}$.
Show that $ |s'_1| + |s'_2| < |s_1 | + |s_2|$. (This should be "obvious", since we're lowering a positive number and increasing a negative number, by a "small enough amount".)
This contradicts the minimality of $ \sum |s_i|$.