Problem 958

Let $a_{1}, \ldots, a_{101}$ be the numbers in the order in which they are written. For any $i$, let $x_{i}$ (respectively $y_{i}$) be the length of the longest increasing (respectively decreasing) subsequence of the sequence $a_{1}, \ldots, a_{101}$ starting at $a_{i}$. Our goal is to show that there exists $i$ such that either $x_{i}$ or $y_{i}$ is greater than or equal to 11. Otherwise, there are at most $10^{2}x_{l}$. Similarly, if $a_{k}>a_{l}$, then $y_{k}>y_{l}$. We thus obtain a contradiction.

Remark: By the same reasoning, we can show more generally that in any sequence of $m n+1$ distinct numbers, we can find an increasing subsequence of length $m+1$ or a decreasing subsequence of length $n+1$. This result is known as the Erdös and Szekeres theorem.

## 3 Thursday afternoon: Pierre Bornsztein

Games and Strategies.