# $m \times n$ persons stand in $m$ rows and $n$ columns

$m \times n$ persons stand as a rectangle of $m$ rows and $n$ columns. Each one is taller than the one next to his left.

Now, if commander orders each column to sort by height, prove that after such sorting, each one is still taller than the one next to his left.

I'm reading a Combinatorics book on my own, but some exercises I can't solve... many thanks!

-

For a person $a$ standing in column $i$, there are $k$ persons in that same column which are taller than him, and since for each person in this column, there is a right neighbor in the next column that's even taller, we now that the $k + 1$-th tallest person in the next column is taller than $a$. After sorting, the right neighbor of $a$ (the $k + 1$-th tallest person of column $i$) is the $k + 1$-th tallest person in column $i + 1$, and this one is thus taller than $a$.

-
How can there be $n$ persons longer than a generic person? That can't be true for the longest of them all. –  joriki Aug 12 '12 at 10:56
I didn't mean the $n$ of the size of the grid, but just a new variable that is the number of person taller than the current one. –  Lieven Aug 12 '12 at 10:58
I see. In that case, you should use a new name for your new variable :-) –  joriki Aug 12 '12 at 11:00
@Lieven thanks a lot, now i got it, after the idea is explained, it's looks so simple! :p thanks again! –  athos Aug 12 '12 at 13:14

(I originally posted a false start by accident.)

Let person in row $r$ and column $c$ be $h_{r,c}$ be $P_{r,c}$, and let the height of that person be $h_{r,c}$. Let $C(r,c)=\{s:h_{s,c}\ge h_{r,c}\}$. Suppose that $1\le c<n$. Then for each $s\in C(r,c)$ we have $h_{r,c}\le h_{s,c}<h_{s,c+1}$. Assume that the columns are sorted so that heights decrease from row $1$ to row $m$. Then $P_{r,c}$ will be in row $|C(r,c)|$ and column $c$ of the new formation. If $c<n$, there are at least $|C(r,c)|$ people in column $c+1$ who are taller than $P_{r,c}$, so the person in row $|C(r,c)|$ and column $c+1$ of the new formation must be taller than $P_{r,c}$.

Added: I see now that Lieven has posted essentially the same argument. I’ll leave this on the off chance that someone finds it easier to follow.

-
@brian-m-scott thanks, both are the same idea and correct! –  athos Aug 12 '12 at 13:15

This is not really a new answer, but places the question in a somewhat broader perspective. Note that the given answers really only consider one pair of adjacent columns at a time, the fact that these are inside a rectangle doesn't really matter. Also one could allow the columns to be of different length, provided that an empty place is considered smaller than any person. The fundamental result is the following.

Define a partial order on the set $A^*$ of words over some ordered alphabet $A$, by comparing corresponding partitions: $(a_1a_2\dots a_n)\geq(b_1b_2\ldots,b_m)$ whenever $n\geq m$ and $a_i\geq b_i$ for all $i\leq m$. Each word determines a multiset of letters (by forgetting the order), and any multiset is represented by a unique word in which the letters are weakly decreasing; this defines a natural "sorting" map $\phi: A^*\to A^*$ whose image is the set of weakly decreasing words. Then $\phi$ is a morphism of paritally ordered sets: for $v,w\in A^*$ one has $v\leq w\implies \phi(v)\leq\phi(w)$. Clearly this applies in particular to sorting two adjacent columns in the matrix of the question. The proof is the one given in the other answers: if letter $k$ of $\phi(v)$ is $a$, then at least $k$ letters of $\phi(v)$, and therefore of $v$, are${}\geq a$, and so by $v\leq w$ at least $k$ letters of $w$ are${}\geq a$, and in particular letter $k$ of $\phi(w)$ is.

The given statement can be made slightly stronger by replacing '$\leq$' by '$<$'; the proof then requires in addition a not-quite-so-easy argument showing that two different permutations of the same multiset of letters cannot be comparable by '$<$'. One way to proceed is to compare for a hypothetical counterexample the sets of positions occupied by the greatest letter; if these sets differ, then both words have some position where they contain the greatest letter and the other word does not, which contradicts them being comparable; if the sets coincide then one can remove all letters in these positions from both words and conclude using induction on the value of the greatest letter.

-