0

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.

Alireza
  • 3
  • 3
  • What have you tried? How far have you gotten? You are more likely to get useful responses if you give us some hint where you are blocked. – Eric Towers Oct 18 '19 at 15:29
  • 1
    This doesn't sound like a pigeonhole principle problem to me. At least not on the face of it. – Arthur Oct 18 '19 at 15:30
  • Sounds like a proof by induction on $n$. – Robert Shore Oct 18 '19 at 15:39
  • This is actually from: R. Brualdi, Introductory Combinatorics, 5th. ed. 2009 Chapter 3: Problem 26. Chapter 3 is dedicated to pigeon hole principle. I don't know where to begin to solve this problem. – Alireza Oct 18 '19 at 16:11

1 Answers1

1

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.

saulspatz
  • 53,131