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.