Pigeonhole height problem?

Question

Ten people of different heights line up in a row. Show that it is always possible to select four of them to step sideways to form a shorter row in which their heights from left to right are either increasing or decreasing.

I have the solution, but I need help understanding why it makes sense.

SOLUTION. Let ak denote the height of the k-th person from the left, for $k = 1,...,10$. We will show that we can select subindices k1 < k2 < k3 < k4 from among {1,2,...,10} such that either ak1 < ak2 < ak3 < ak4 (Case 1: increasing heights) or else ak1 > ak2 > ak3 > ak4 (Case 2: decreasing heights). To see this, assume that there do not exist 4 subindices giving increasing heights (Case 1). We will show we can then find 4 subindices giving Case 2. Define mk to be the length of the longest subsequence of increasing heights to the right, starting at position k. Then 1 ≤ mk ≤ 3, since Case 1 never holds. So we have 10 integers {m1,m2,...,m10}, each of which is 1,2 or 3. Consequently the Generalized Pigeonhole Principle implies that at least 4 of them are equal, say mk1 = mk2 = mk3 = mk4. But this implies that Case 2 is valid for these indices. To see this, note for instance that mk1 = mk2 implies ak1 > ak2, since otherwise mk1 would be strictly greater than mk2.

Okay, so assuming that there will never be a case where you can pick 4 people and get increasing heights, that means that the longest subsequence is 3. I understand up to these part. But why would you assign the values 1, 2 or 3 to ten different integers? How do we even get these 10 integers to assign 1, 2, or 3 subsequences from? I also understand from basic pigeonhole principle that at least 4 of them must be equal. So if at least 4 of them have the same subsequences, how would that imply that if you pick 4 people, they would be from increasing to decreasing.

Answer 1

Okay, I am going to show you a really simple way to prove this by means of an example:

Assume each height is different (this seems to be implicit in the question) then each person's height can be ranked from 1 to 10 (shortest to tallest). Thus each queue can be viewed as a permutation of $\{1,2,\ldots , 10\}$.

Next assign to each number $k$ in the permutation a pair of positive integers $x_k$ and $y_k$ defined by:

1. $x_k$ is the length of the longest increasing subsequence beginning with $k$.
2. $y_k$ is the length of the longest decreasing subsequence ending with $k$.

So now consider, for example, the permutation

$$4,6,3,7,8,2,10,9,1,5$$ We can write this permutation with its pairs $x_k$ and $y_k$:

\begin{array}{c|cccccccccc} k & 4 & 6 & 3 & 7 & 8 & 2 & 10 & 9 & 1 & 5\\ \hline x_k & 5 & 4 & 4 & 3 & 2 & 2 & 1 & 1 & 2 & 1\\ y_k & 1 & 1 & 2 & 1 & 1 & 3 & 1 & 2 & 4 & 3 \end{array}

E.g. The longest increasing subsequences beginning with 4 are $4,6, 7, 8, 10$ and $4,6,7,8,9$ (both length $x_4=4$) and the longest decreasing subsequences ending in 2 are $4,3,2$ or $6,3,2$ (both length $y_2=3$).

Now, it should be clear that, for any permutation, there are no two equal ordered pairs $(x_k,y_k)$. For, supposing there are two equal ordered pairs for $k$ and $k'$: $(x_k,y_k)=(x_{k'},y_{k'})$, where $k$ is to the left of $k'$ in the permutation. Then either

• $k>k'$ in which case we may include $k'$ in the longest decreasing subsequence ending with $k$ (length $y_k$) so that $y_{k'}>y_k$ contradicting our assertion, or
• $k<k'$ in which case we may include $k$ in the longest increasing subsequence beginning with $k'$ (length $x_{k'}$) so that $x_k>x_{k'}$, another contradiction.

So now our pigeonholes are boxes labelled with the coordinates $(x_k,y_k)$ and we fill them with our permuted ranks (our pigeons: 1 to 10). In this case

\begin{array}{c|c|c|c|c|c|} \hline y_k=6&&&&&\\ \hline y_k=5&&&&&\\ \hline y_k=4 & & 1 & & &\\ \hline y_k=3 & 5 & 2 & & &\\ \hline y_k=2 & 9 & & & 3 &\\ \hline y_k=1 & 10 & 8 & 7 & 6 & 4\\ \hline & x_k=1 & x_k=2 & x_k=3 & x_k=4 & x_k=5&x_k=6\\ \end{array}

Since each pigeonhole contains a unique rank from 1 to 10 we must conclude that if we were to try and minimise the maximum lengths of increasing and decreasing subsequences, the best we could do is fit 9 of our height ranks into the set of $3\times 3$ pigeonholes in the bottom left hand corner. Then there would always be 1 rank remaining which must have either $x_k$ or $y_k$ greater than or equal to $4$ (I.e. outside the bottom left $3\times 3$ set of pigeonholes).

In general we can see from our 2D array of pigeonholes that for a permutation of $\{1,2,\ldots ,n\}$ there will always be at least one increasing or decreasing subsequence of at least length $\left\lfloor \sqrt{n}\right\rfloor +1$.

Answer 2

The values you assign in the pigeonholing phase represent the largest possible increasing run to that point. Any time you assign the same value to two numbers, those two must in decreasing order, otherwise the second could have been added to the sequence defined by the first to assign a value 1 greater. Similarly if a third number also is assigned this value, it must be less than both the previous numbers assigned this value (otherwise again would get a higher number), so would continue a decreasing sequence with them.