Suppose that the mn people of a marching band are standing in a rectangular formation of m rows and n columns in such a way that in each row each person is taller than the one to his or her left. Suppose that the leader rearranges the people in each column in increasing order of height from front to back. Show that the rows are still arranged in increasing order of height from left to right.
Thanks in advance.
Consider a person a $P$ in row $j$, column $k$, where $k>1$. When the rows were sorted, there was a person shorter than $P$ on $P$'s left, and this person is still in column $k-1$. Likewise, each of the $j-1$ people in front of $P$ had a shorter person on his left, and those people are still in column $k-1$. Note that $P$ is taller than all these people (because they're shorter than people shorter than $P$) so there are at least $j$ people in column $k-1$ shorter than $P$. Since column $k-1$ was just sorted, the $j$ shortest people are in front, so $P$ is taller than the person on his left.