Partitions et théorème de Dilworth

Soit $S$ un ensemble de $mn+1$ entiers distincts.

1. Montrer qu'il existe une suite croissante de longueur $m+1$ ou une suite décroissante de longueur $n+1$ dans $S$ (théorème d'Erdős-Szekeres).
2. Montrer que ce résultat est optimal : il existe un ensemble de $mn$ entiers sans suite croissante de $m+1$ ni décroissante de $n+1$.
3. Appliquer ce résultat pour $m=n=4$ : toute permutation de 17 entiers possède une sous-suite monotone de longueur 5.