Théorème de Hales-Jewett

Une description géométrique informelle du théorème est la suivante : pour tous entiers positifs n et c, il existe un nombre H tel que si les cellules d'un cube de côté n en dimension H sont colorées en c couleurs, il existe une ligne, une colonne ou une diagonale (dans un sens précisé ci-dessous) de longueur n dont toutes les cellules sont de la même couleur. En d'autres termes, la généralisation du jeu de morpion ou tic-tac-toe en dimension supérieure, et multi-joueurs, ne peut pas se terminer par un match nul, quelle que soit la taille de n, quel que soit le nombre c de joueurs, et quel que soit l'ordre des joueurs, à la seule condition qu'il soit joué sur un plateau de dimension H suffisamment élevée. Par un argument de vol de stratégie (en) standard, on peut alors conclure que si deux joueurs alternent, alors le premier joueur possède une stratégie gagnante lorsque H est suffisamment grand, bien qu'aucun algorithme pratique pour obtenir cette stratégie ne soit connu.

Soit ${\displaystyle W_{n}^{H}}$ l'ensemble des mots de longueur H sur un alphabet de n lettres ; c'est-à-dire l'ensemble des suites de longueur H à éléments dans {1, 2, ..., n }. C'est cet ensemble qui est l'hypercube objet du théorème.

Un mot variable ${\displaystyle w(x)}$ sur ${\displaystyle W_{n}^{H}}$ est un mot de longueur H qui contient un élément spécial x à la place d'au moins une des lettres. Les mots ${\displaystyle w(1),w(2)\ldots ,w(n)}$ obtenus en remplaçant toutes les instances de l'élément spécial x respectivement par 1, 2, ..., n, forment une droite combinatoire dans l'espace ${\displaystyle W_{n}^{H}}$ ; les droites combinatoires correspondent aux lignes, aux colonnes et à (certaines des) diagonales de l'hypercube. Le théorème de Hales-Jewett s'énonce alors comme suit :

Si on identifie les joueurs à la couleur de leurs pions, le théorème assure l'existence d'une droite combinatoire monochrome.

Soient n = 3, H = 2 et c = 2. L'hypercube ${\displaystyle W_{n}^{H}}$, dans ce cas, est simplement de le plateau du morpion usuel, avec ses neuf positions :

11	12	13
21	22	23
31	32	33

Un exemple de droite combinatoire est le mot ${\displaystyle 2x}$, qui correspond à la droite 21, 22, 23 ; une autre droite combinatoire est ${\displaystyle xx}$, qui est la droite 11, 22, 33. (la droite 13, 22, 31, bien qu'une droite valide pour le morpion, n'est pas représenté par une droite combinatoire). Dans ce cas particulier, le théorème de Hales-Jewett ne s'applique pas ; il est possible de diviser le plateau du morpion en deux ensembles, par exemple {11, 22, 23, 31} et {12, 13, 21, 32, 33}, dont aucun ne contient une droite combinatoire (et correspondrait à un match nul au jeu de tic-tac-toe). D'un autre côté, si on augmente H à 8 par exemple (de sorte que le plateau est maintenant en dimension huit, avec 3 ⁸ = 6561 positions), et si on divise ce plateau en deux ensembles (les "zéros" et les "croix"), alors l'un des deux ensembles doit contenir une droite combinatoire (c'est-à-dire qu'un mouvement gagnant est possible dans cette variante du tic-tac-toe).