Partitions et théorème de Dilworth

Solution

1. Théorème d'Erdős-Szekeres :
   Soit $a_1, a_2, \ldots, a_{mn+1}$ la suite. Pour chaque $i$, soit $c_i$ la longueur de la plus longue sous-suite croissante commençant en $a_i$.
   Supposons que toutes les sous-suites croissantes maximales soient de longueur $\le m$. Alors les $c_i \in \{1, \ldots, m\}$.
   Par le principe des tiroirs, $mn+1$ valeurs dans $m$ cases : il existe $n+1$ indices $i_1 < i_2 < \cdots < i_{n+1}$ avec $c_{i_1} = c_{i_2} = \cdots = c_{i_{n+1}}$.
   Mais si $i < j$ et $a_i < a_j$, alors $c_i > c_j$ (contradiction). Donc $a_{i_1} > a_{i_2} > \cdots > a_{i_{n+1}}$ : sous-suite décroissante de longueur $n+1$. ✓
2. Optimalité :
   Prendre les $mn$ entiers arrangés en $n$ blocs décroissants de $m$ entiers chacun, avec chaque bloc plus petit que le précédent.
   Ex. pour $m=n=2$ : $(4,3,2,1)$ arrangé comme $(4,3),(2,1)$ donne $(4,3,2,1)$ : suite $4,3,2,1$ ou $4,2$.
3. Pour $m = n = 4$, $mn+1 = 17$ :
   Par le théorème, toute permutation de 17 entiers distincts possède une sous-suite croissante de longueur 5 ou décroissante de longueur 5. Dans les deux cas, une sous-suite monotone de longueur 5. ✓