Arranging numbers in an array (Swedish Math Olympiad 1986)

Question

Consider an $m\times n$ array of real numbers. Let $d>0$. Suppose that the difference between the maximum number and the minimum number in each row is at most $d$. We then sort the numbers in each column so that the maximum element is in the first row and the minimum element is in the last row (so each column is arranged in decreasing order). Show that the difference between the maximum number and the minimum number in each row (after the change) is still $\le d$.

Source : Swedish Math Olympiad 1986, also Principles and Techniques in Combinatorics

Here is my attempt. Let $M_k$ and $m_k$ be the original largest and smallest elements of the $k$th row. Let $M'_k$ and $m'_k$ be the new largest and smallest elements of the $k$th row. We have $M'_1\ge M'_2 \ge ... \ge M'_m$ and $m_1'\ge m_2' \ge ... \ge m'_m$. Let's try induction on $k$.

For $k=1$, suppose that $M'_1$ was originally in row $i$. Then $M'_1\le M_i$. We know that $m'_1$ is in the same column as some element originally from row $i$. Let that element be $a_i$. Therefore $m'_1\ge a_i\ge m_i$ so $M'_1-m'_1\le M_i-m_i\le d$.

Let $1<k\le m$. Suppose that $M'_k$ was originally in row $i$ so $M'_k\le M_i$. We know that $m'_k$ is in the same column as some element $a_i$ originally from row $i$. Suppose that $a_i$ is in row $j$ after the change. If $j\ge k$, then $m'_k\ge a_i\ge m_i$ so $M'_k-m'_k\le M_i-m_i\le d$. We now assume $j<k$. What to do here?

BTW in the book "Principles and Techniques in Combinatorics" this problem is in chapter 3 which is about pigeonhole principle. So if you have a solution with pigeonhole that'd be great.

Answer 1

Here's an approach, but it doesn't use PP.

Claim: Given $n$ intervals $[a_i, a_i + d]$ on the real line.
In each interval, one real number $b_i$ is chosen.
Sort the $a_i, b_i$ in increasing order to get the sequences $a'_i, b'_i$
Then, $ b'_k \in [ a'_k , a'_k + d]$.

Proof: Do this yourself. If stuck, show what you've tried.
Show that $b'_k \geq a'_k$. Prove by contradiction.
Show that $b'_k \leq a'_k+d$. Prove by contradiction.

Corollary: The problem holds.

Let $ a_i = \min_k m_{i, k}$ be the minimum in each row.
Add an additional $n+1$st column, with entries $m_{i,n+1} =d + a_i$.

Fix a column $k$.
By definition, each element $m_{i, k} \in [a_i, a_i + d]$.
Now, apply the claim to conclude that $m'_{i, k}\in [a'_k, a'_k + d] \quad \forall i$.

Fix a row $i$.
We have $m'_{i, k } \in [a'_k, a'_k + d] \quad \forall k$,
Hence, the difference between the max and min in each row (for $n+1$ columns) is still $ \leq d$.
Hence, the difference between the max and min in each row (for $n$ columns) is still $ \leq d$.

---

Note: In the claim, I used intervals of exactly length $d$ to ensure that we could sort the intervals cleanly. Otherwise, we could have nested intervals, and then it might not be clear how to sort the rows in increasing order.

As it turns out, this was unnecessary. We have a stronger claim:

Given $n$ intervals $[a_i, b_i]$, with elements $c_i \in [a_i, b_i]$, and we sort each individual sequence $a_i, b_i, c_i$ in increasing order, then $ c'_i \in [a'_i, b'_i]$.

Note: If we sorted the intervals just by the first coordinate, then the claim need not be true. IE $c'_i \not \in [a_{i'}, b_{i'}]$.

However, I can't apply the stronger claim to the problem. Any help here is greatly appreciated. The trouble that I run into is that ultimately, we still have to show that $ b'_i - a'_i \leq d$. While this is recognizable as the 2 column case, it is essentially the entire argument (IE the induction on the number of columns is trivial).

My solution avoids this because $b'_i - a'_i = d$ by construction. Doing so felt a bit forced / unnatural, though I know why I thought of doing it.

Answer 2

Here is another approach, though it again doesn't use PP.

We first prove the 2 column case. Consider the bipartite graph, with vertices represented by these values in each column, and we draw an edge between 2 values in different columns if their difference is at most $d$.

Observe that each $a_i$ is connected to (at least the) corresponding $b_i$.
For a subset $C$ consisting of vertices in a column, let $Im(C)$ be the vertices that they are connected with. Then, the previous observation establishes $ |C| \leq |Im(C)|$.

Now, when we re-arrange the columns, suppose that $a_i'$ is not connected to $b_i'$.
$a_i'$ is connected to some $b_k'$. Let the minimal index be $K$, and $ i \neq K$.
WLOG $i < K$. (The case of $i>K$ can be dealt with similarly.)
Then, with $C = \{b_1', b_2', \ldots b_{K-1}'\}$, $Im(C) \subset \{a_1', a_2', \ldots a_{i-1}'\}$.
This gives us $|C| > |Im(C)|$, which is a contradiction.
Hence, $a_i'$ is connected to $b_i'$, so their difference is at most $d$.

Now, for the general $n-$column case, the above establishes that for any 2 columns, the rearranged columns have entries with difference at most $d$ in each row. Hence, this is true for the entire row.