De l'ordre dans les nombres

On considère les n2 + 1 premiers nombres entiers, écrits dans un ordre quelconque.
On a donc une suite a1, a2, a n2 + 1.
Prouvons que, dans cette suite, il y a au moins n + 1 nombres qui sont placés en ordre ( croissant ou décroissant).

Pour chaque aj., on note N(aj) le nombre de termes de la plus longue sous-suite croissante commençant par aj .
Supposons qu'il n'existe pas de sous-suite croissante de n + 1 termes.
Chacun des n2 + 1 indices N(aj), prend alors ses valeurs dans 1,2,...n. Intéressons-nous aux effectifs correspondants :
Valeurs 123...n
Effectifs k1k2k3...kn
Si chaque kj était inférieur ou égal à n, l'effectif total ne dépasserait pas n2. Il existe donc au moins n +1 termes, correspondant à une même valeur de N. Appelons b1.. b2... bn+1, n + 1 de ces termes, tels qu'ils sont placés dans la suite de départ.
On ne peut avoir b1< b2 . En effet si r est le nombre de termes maximal pour les sous-suites croissantes commençant par b2 , il y aurait alors une sous-suite croissante de r + 1 termes commençant par b1, or N(b1)=N( b2)=r. On a donc b1> b2.
On démontre de la même façon que b2 > b3 , et ainsi de suite, d'où b1> b2 > b3...> bn+1 .
Conclusion : S'il n'existe pas de sous-suite croissante de n + 1 termes, il existe une sous-suite décroissante de n+1 termes au moins.