Monotone subsequences (Erdős–Szekeres)

Idea. Label every term by two numbers, and show that the labels never repeat.

Distinct labels. Let $i<j$.
- If $a_i<a_j$, any increasing subsequence ending at $a_i$ can be extended by $a_j$, so $x_j\ge x_i+1$.
- If $a_i>a_j$, any decreasing subsequence ending at $a_i$ can be extended by $a_j$, so $y_j\ge y_i+1$.

In both cases $(x_i,y_i)\ne(x_j,y_j)$.

Counting. Suppose, for contradiction, that all increasing and decreasing subsequences have length at most $n$. Then $1\le x_i,y_i\le n$ for all $i$, so there are at most $n^2$ possible pairs. But we have $n^2+1$ terms with pairwise distinct pairs: contradiction.

Remark. The bound $n^2+1$ is sharp.

Lesson. When pigeonhole directly fails, build a cleverly chosen label for each object so that distinct objects get distinct labels.