Collection of numbers always in increasing or decreasing order

Question

Anyone have any ideas on this question? I think you have to use the pigeon hole principle..but I am not sure about that?

The numbers $1,2,3,\ldots,101$ are written down in a row in some order. Is it always possible to cross out $90$ numbers in a way such that all $11$ numbers left will stay either in increasing or decreasing order?

Answer 1

This is the Erdos-Szekeres theorem on monotonic subsequences. I'm pasting a proof from wikipedia:

Given a sequence of length $(r − 1)(s − 1) + 1$, label each number $n_ i$ in the sequence with the pair $(a_i,b_i)$, where $a_i$ is the length of the longest monotonically increasing subsequence ending with $n_i$ and $b_i$ is the length of the longest monotonically decreasing subsequence ending with $n_i$. Each two numbers in the sequence are labeled with a different pair: if $i < j $ and $n_i < n_j$ then $a_i < a_j$, and on the other hand if $n_i > n_j$ then $b_i < b_j$. But there are only $(r − 1)(s − 1)$ possible labels in which $a_i$ is at most $r − 1$ and $b_i$ is at most $s − 1$, so by the pigeonhole principle there must exist a value of $i$ for which $a_i$ or $b_i$ is outside this range. If $a_ i$ is out of range then $n_i$ is part of an increasing sequence of length at least $r$, and if $b_i$ is out of range then $n_i$ is part of a decreasing sequence of length at least $s$.

in your problem, take $r = s = 11$

suggested reading... some further exploration of monotonic subsequences: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v4i2r14

Answer 2

Associate with each element of the list an ordered pair $(a,b)$ where $a$ is the longest increasing subsequence ending on that number and $b$ is the longest decreasing subsequence starting with that number. Show that no two numbers can have the same pair associated because one can extend the subsequence of the other. There are only $100$ pairs with both entries $10$ or less.