Show that if there are 101 people of different heights standing in a line

Question

Show that if there are 101 people of different heights standing in a line, it is possible to find 11 people in the order they are standing in the line with heights that are either increasing or decreasing.

Answer 1

Define a partial order on the set of people by stipulating that $x\lt y$ means that person $x$ is shorter than $y$ and is standing behind $y$. The question asks us to show that this partially ordered set of size $101$ contains either a chain or an antichain of size $11$. The simpler way to do this is to observe that a partially ordered set, which contains no $11$-element chain, is the union of $10$ antichains, one of which must contain more than $10$ elements by the pigeonhole principle. The fancier alternative is to quote Dilworth's chain decomposition theorem: if there is no $11$-element antichain, then the poset is the union of $10$ chains, etc.

Answer 2

This is a straight-forward application to the pigeonhole principle. In fact a more general statement holds:

If $a_1,\ldots,a_{n^2+1}$ is a sequence of $n^2+1$ real numbers then it must contain either an increasing or a decreasing subsequence of length $n+1$.

For a proof see for example this.

Answer 3

This is a special case of the Erdős-Szekeres theorem with $r = s = 11$.

Here is a proof for this special case. I am assuming that no two people have the same height. For the $i$:th person $P_i$ in the line, we let $x_i$ be the length of the longest sequence of people behind $P_i$ which are increasing in height (including $P_i$). We let $y_i$ be the length of the longest sequence of people in front of $P_i$ which are decreasing in height (including $P_i$).

Now, for $i < j$ we have $(x_i,y_i) \neq (x_j,y_j)$. This follows from the fact that if $P_i$ is shorter than $P_j$ then the longest sequence of increasing heights ending at $P_i$ can be used to build a longer sequence ending at $P_j$, so $x_i < x_j$, or if $P_i$ is taller than $P_j$, the longest sequence of decreasing heights after $P_j$ can be used to build a longer sequence of decreasing heights after $P_i$, so $y_i > y_j$.

Thus, we have 101 different tuples of numbers. We can place these into a grid of $101 \times 101$ pigeonholes, and we place $(x_i,y_i)$ into the pigeonhole at $(x_i,y_i)$. Each pigeonhole gets at most one tuple, since $(x_i,y_i) \neq (x_j, y_j)$. But we see that we have more tuples than fit into a $10 \times 10$ grid of pigeonholes, meaning that at least one tuple has $x_i > 10$ or $y_i > 10$, meaning that there is a subsequence of at least 11 people with decreasing or increasing heights.