Dans cet article nous nous adonnerons à notre passe-temps favori : colorier les entiers tout en respectant certaines contraintes fixées d’avance. Activité ludique, certes, mais aussi source de défis considérables pour la recherche mathématique, comme on a pu le voir dans deux récents articles de cette rubrique : Les nombres de Schur, des centenaires pleins d’avenir et Les extraordinaires prédictions du Révérend Walker.

Triplets pythagoriciens

Commençons par présenter les objets mathématiques concernés par nos contraintes sur les coloriages. Ces objets sont les triplets pythagoriciens, c’est-à-dire les triplets de nombres entiers non nuls $(a,b,c)$ satisfaisant l’égalité
\[ a^2+b^2 = c^2. \]
L’exemple le plus simple de triplet pythagoricien est $(3,4,5)$ : il est bien constitué de nombres entiers non nuls, et il vérifie bien l’égalité $3^2+4^2=5^2$ puisque $9+16=25$.

L’un des plus puissants outils de la pensée mathématique — ou de la pensée tout court — est celui de chercher à considérer un même objet ou concept de plusieurs points de vue différents. Les mathématiques en font un usage intensif pour leur plus grand bénéfice. Par exemple, les liens intimes entre algèbre et géométrie sont une source fantastique d’enrichissement mutuel entre ces deux branches.

Interprétation géométrique

Les triplets pythagoriciens, justement, peuvent être vus en même temps [1] comme des objets algébriques — ou arithmétiques — et géométriques. Du point de vue géométrique, ils sont bien sûr intimement liés au Théorème de Pythagore portant sur les longueurs des côtés des triangles rectangles.

À titre d’illustration, la figure ci-dessous représente le triplet pythagoricien $(3,4,5)$. Les deux petits côtés de ce triangle rectangle sont de longueur $3$ et $4$ respectivement, tandis que l’hypoténuse est de longueur $5$ :

À part $(3,4,5)$, existe-t-il d’autres triplets pythagoriciens ? Autrement dit, d’autres triangles rectangles dont les trois côtés soient tous de longueur entière ?

L’humanité s’intéresse à cette question depuis au moins 3800 ans, soit bien avant Pythagore, comme en témoigne la fameuse tablette d’argile Plimpton 322 :

Un article sur ce site de Christine Proust est consacré à cette tablette d’argile et à son interprétation.

Infinité

Eh bien oui, il existe de nombreux autres triplets pythagoriciens. À partir de $(3,4,5)$, il est facile d’en produire de nouveaux, par exemple $(6,8,10)$ comme on le vérifie aisément. Il a suffi de tout multiplier par $2$.

C’est d’ailleurs un principe général : pour tout entier naturel $n$, le triplet $(3 n,4 n,5 n)$ est pythagoricien.

Il y a donc une infinité de triplets pythagoriciens. Cela dit, géométriquement, il n’y a guère de différence entre les triplets pythagoriciens $(3,4,5)$ et $(3n,4n,5n)$, puisque les triangles rectangles correspondants sont semblables. Cela se voit bien sur cette figure représentant le triplet $(6,8,10)$ :

Alors, y a-t-il d’autres triplets pythagoriciens à part $(3n,4n,5n)$, qui soient géométriquement différents ? Oui. Par exemple $(5,12,13)$, qui est bien pythagoricien puisque \[5^2+12^2=25+144=169=13^2.\] Et le triangle rectangle correspondant est bien différent de celui représentant $(3,4,5)$ :

Mais encore ? Fait remarquable, il y a une infinité de triplets pythagoriciens géométriquement distincts deux à deux, et on les connaît tous ! Leur description complète est donnée plus loin.

Présentation du jeu

L’un des buts de cet article est d’attirer l’attention des lecteurs sur un aspect fascinant des triplets pythagoriciens : non seulement ils préoccupent l’humanité depuis des millénaires, mais aujourd’hui encore, ils continuent à poser d’énormes défis à la recherche mathématique. Le jeu de coloriage que nous allons maintenant présenter en témoigne abondamment.

Voici les règles de ce jeu. Celui-ci est de nature collaborative, son seul but étant d’obtenir le meilleur score $N$ possible.

• Règle 1 :
  on colorie les entiers $1,2,3,4,\dots$ avec deux couleurs, disons rouge et bleu.

• Règle 2 :
  pour qu’un coloriage des entiers $1,2,3,\dots,N$ soit accepté, chaque triplet pythagoricien $(a,b,c)$ dont les constituants $a,b,c$ n’excèdent pas $N$ doit être mixte, c’est-à-dire comporter à la fois un membre rouge et un membre bleu.

• Règle 3 :
  le score d’une session particulière du jeu est le plus grand $N$ atteint en respectant les règles 1 et 2.

Inventé il y a plusieurs décennies, ce jeu continue de mobiliser les chercheurs pour déterminer la ou les meilleures stratégies possibles. Plus précisément, on souhaite pouvoir répondre aux questions fondamentales suivantes.

Questions.

• Comment atteindre un score $N$ aussi élevé que possible ?
• Existe-t-il un score maximal, c’est-à-dire un score impossible à dépasser ?

Voici les meilleurs scores atteints ces dix dernières années, fruits d’intenses travaux en équipe principalement.

Génération des triplets pythagoriciens

Comme observé plus haut, il y a une infinité de triplets pythagoriciens, et en plus on les connaît tous.

Comment décrire cette collection infinie ? Grâce à la puissance de la paramétrisation. Autrement dit, on peut obtenir tous les triplets pythagoriciens $(a,b,c)$ grâce à des formules exprimant $a,b,c$ en termes de trois paramètres formels $u,v,n$ choisis librement. Voici la recette, connue depuis des temps immémoriaux.

Recette. Tout triplet pythagoricien $(a,b,c)$ peut s’obtenir de la façon suivante. Choisir trois entiers naturels quelconques $u,v, n$, avec $u$ strictement plus grand que $v$, et poser :
\[a=n \times \color{blue}{(u^2-v^2)}, \quad b=n\times \color{blue}{2uv},\quad c=n\times \color{blue}{(u^2+v^2)}.\]

Par exemple, notre triplet favori $(3,4,5)$ s’obtient à partir de cette recette en posant $\color{blue}{u=2}$, $\color{blue}{v=1}$ et $n=1$.

Jusqu’à hauteur $20$

Déterminons maintenant la collection $C$ de tous les triplets pythagoriciens constitués d’entiers naturels inférieurs ou égaux à $20$.

Pour ce faire, on dispose d’une recette, alors appliquons-la ! Il s’agit donc de choisir des nombres entiers naturels $u,v,n$ avec $u > v$ de façon à ce que les termes $a,b,c$ résultants restent confinés sous $20$.

Sachant que $c=n(u^2+v^2)$, et que les carrés croissent très vite, les seules valeurs admissibles pour $u$ et $v$ sont à prendre parmi $1,2,3,4$. En effet, à partir de $5$ ça ne convient plus, puisque $5^2$ dépasse $20$.

Les tableaux ci-dessous donnent les différents triplets obtenus lorsque $u$ et $v$ parcourent $1,2,3,4$.

— Pour $n=1$, nous obtenons le tableau suivant. Les cases vides correspondent aux valeurs de $u$ et $v$ ne vérifiant pas la condition requise $u>v$.

Le triplet $\color{red}{(7,24,25)}$ est à exclure puisque $24$ et $25$ dépassent $20$.

— Pour $n=2$, nous n’obtenons pas de nouveaux triplets de $C$.

— Pour $n=3$, nous obtenons un seul nouveau triplet dans $C$, à savoir $(9,12,15)=3\times(3,4,5)$.

Pour $n=4$, il s’avère que seul le triplet $4\times(3,4,5)=\color{blue}{(12,16,20)}$ est admissible dans $C$, mais il avait déjà été obtenu avec $n=1$.

Quant aux valeurs supérieures de $n$, elles ne donneront plus que des triplets trop grands et donc en dehors de $C$.

Voilà notre quête terminée ! La collection $C$ des triplets pythagoriciens entre $1$ et $20$ est composée des six membres suivants :

\[ C \, = \, (3,4,5), \, (5,12,13), \, (6,8,10), \, (8,15,17), \, (9,12,15), \, (12,16,20).\]

Voici une représentation de leurs triangles rectangles correspondants.

Un score de $20$

Voyons maintenant comment obtenir un score de $20$ à notre jeu.
Nous devons colorier en rouge ou bleu chaque nombre entier entre $1$ et $20$ de telle sorte que tous les triplets dans $C$ soient mixtes.

Observons tout d’abord que les entiers $1,2,7,11,14,18$ et $19$ n’apparaissent dans aucun triplet de $C$ ; il n’y a donc aucune contrainte sur le choix de leurs couleurs.

Comme $(3,4,5)$ apparaît dans $C$, il doit être mixte, et donc $3$, $4$ et $5$ ne doivent pas recevoir la même couleur. Par exemple, colorions $3$ et $4$ en bleu et $5$ en rouge :

\[C \, = \, (\color{blue}{3},\, \color{blue}{4},\, \color{red}{5}), \, (\color{red}{5},12,13), \, (6,8,10), \, (8,15,17),\, (9,12,15), \, (12,16,20).\]

Pour le second triplet, nous choisissons de colorier $12$ et $13$ en bleu :

\[C\, = \, (\color{blue}{3},\, \color{blue}{4},\, \color{red}{5}),\, (\color{red}{5},\, \color{blue}{12},\, \color{blue}{13}),\, (6,8,10), \, (8,15,17),\, (9,\color{blue}{12},15),\, (\color{blue}{12},16,20).\]

Pour les cinquième et sixième triplets, nous choisissons de colorier $9$ et $16$ en bleu et $15$ et $20$ en rouge :

\[C=(\color{blue}{3},\color{blue}{4},\color{red}{5}), (\color{red}{5},\color{blue}{12},\color{blue}{13}), (6,8,10), (8,\color{red}{15},17), (\color{blue}{9},\color{blue}{12},\color{red}{15}), (\color{blue}{12},\color{blue}{16},\color{red}{20}).\]

Terminons en coloriant par exemple $6,8$ en bleu et $10,17$ en rouge :

\[C=(\color{blue}{3},\color{blue}{4},\color{red}{5}), (\color{red}{5},\color{blue}{12},\color{blue}{13}), (\color{blue}{6},\color{blue}{8},\color{red}{10}), (\color{blue}{8},\color{red}{15},\color{red}{17}), (\color{blue}{9},\color{blue}{12},\color{red}{15}), (\color{blue}{12},\color{blue}{16},\color{red}{20}).\]

Le coloriage
\[ 1,2,\color{blue}{3},\color{blue}{4},\color{red}{5},\color{blue}{6},7,\color{blue}{8},\color{blue}{9},\color{red}{10},11,\color{blue}{12},\color{blue}{13},14,\color{red}{15},\color{red}{17},18,19,\color{red}{20}, \]
où les nombres en noir sont coloriés indifféremment en rouge ou bleu, satisfait les règles du jeu et fournit donc un score de $20$.

Amélioration du score

Obtenir ce score de $20$ a été plutôt facile. On peut l’améliorer en travaillant un petit peu plus. Essayez donc d’obtenir un score de $50$.

L’apparente simplicité de ce jeu est trompeuse. Arriver jusqu’à $20$ ou $50$, passe encore. Mais ça se complique assez vite : les choix de couleurs que l’on fait au début finissent par conduire à des blocages, c’est-à-dire à des triplets pythagoriciens non mixtes ou monochromatiques ; il faut donc explorer de nouveaux choix pour espérer éviter ceux-ci et aller plus haut.

Pour accrocher leurs noms au tableau des meilleurs scores, nos champions ont eu recours à des méthodes très sophistiquées, même avec l’appui intensif d’ordinateurs.

Mixité et antijeu

Notre jeu est typique d’une théorie appelée Théorie de Ramsey, due à un jeune mathématicien anglais de génie disparu prématurément, Frank Plumpton Ramsey [1903-1930]. Avant la naissance de cette théorie vers 1929, deux exemples annonciateurs avaient déjà vu le jour, l’un par David Hilbert en 1892, l’autre par Issai Schur en 1916.

Dans sa forme la plus générale, il s’agit du problème suivant : on part d’un certain objet mathématique, on colorie ses éléments constitutifs d’un nombre donné de couleurs, et on se demande si l’on va nécessairement trouver un sous-objet de même nature qui soit monochromatique, c’est-à-dire dont les éléments constitutifs sont tous de même couleur.

Par exemple, considérons le graphe complet à $6$ sommets, et colorions ses arêtes de façon arbitraire en deux couleurs rouge et bleu. Un résultat de base de la Théorie de Ramsey dit alors que nécessairement, on verra émerger un triangle monochromatique, avec donc ses trois arêtes toutes rouges ou toutes bleues.

À titre d’illustration, voici une tentative de coloriage partiel de ce graphe, sans aucun triangle monochromatique à ce stade :

Il ne manque plus que les deux arêtes encore noires à colorier. Or dès que l’on colorie l’une ou l’autre en rouge ou bleu, un triangle monochromatique émerge. C’est inévitable, même en partant de n’importe quel autre coloriage partiel, comme démontré par la théorie.

Par contre, pour le graphe complet à $5$ sommets seulement, il est tout à fait possible de colorier ses arêtes en deux couleurs en évitant tout triangle monochromatique. Essayez, vous verrez !

Y a-t-il un score maximal ?

Revenons à notre jeu et à la question fondamentale posée au début : admet-il, oui ou non, un score maximal ?

Le mathématicien Ronald Graham a même proposé une récompense de 100 dollars pour la première personne qui répondrait à cette question.

Pour établir l’existence d’un score maximal $M$, il s’agit de montrer que quel que soit le coloriage en deux couleurs des entiers $1,2,\dots,M+1$, il y aura forcément au moins un triplet pythagoricien $(a,b,c)$ avec $a,b,c$ compris entre $1$ et $M+1$ qui sera monochromatique, c’est-à-dire tout rouge ou tout bleu.

Rien ne dit a priori qu’un tel score maximal existe. On l’a vu dans le tableau du début, le meilleur score actuel est de $7824$, obtenu en 2016 par l’équipe numéro $1$. Mais après tout, peut-être qu’avec beaucoup d’astuce et de chance, on pourrait obtenir un score de un million ou plus encore.

Eh bien non, toute l’astuce du monde n’y suffirait pas ! Car l’équipe numéro 1 a fait bien plus qu’obtenir le score de $7824$ : elle a montré, par calculs sur ordinateur aussi massifs qu’audacieux, que le score de $7825$ est impossible à atteindre. Autrement dit, que notre jeu admet bien un score maximal $M$, et que celui-ci vaut exactement
\[ M=7824. \]
Le coloriage admissible des entiers de $1$ à $7824$ obtenu par l’équipe numéro 1 est visible ici.

Preuve de la maximalité

Comment se convaincre que le score de $7825$ est inatteignable ? C’est extrêmement difficile, et pour tout dire impossible sans ordinateur dans l’état actuel de nos connaissances. Même par ordinateur, c’est loin d’être du gâteau ! La preuve donnée par notre équipe gagnante repose sur un calcul effectué à l’aide d’un solveur SAT sur un super ordinateur de 800 cores — soit environ 200 ordinateurs performants du marché — pendant 2 jours.

Pour balayer d’emblée tout doute quant à la validité de leur affirmation, les auteurs ont accompagné leur calcul d’un certificat [7] prouvant que celui-ci est correct.

Petit problème, ce certificat pèse 200To [8] — soit la capacité de 100 disques durs de 2To équipant les bons ordinateurs actuels — mais pouvant heureusement être compressé en un fichier de 68Go [9]. Une paille, quoi.

Cela dit, leur travail met brillamment fin à notre jeu. L’équipe numéro 1 en sera la gagnante à vie. Pour l’anecdote, celle-ci a bien reçu de Ronald Graham la récompense de 100 dollars promise.

Passons à trois couleurs

Pour ne pas en rester là, modifions la Règle 1 en passant à trois couleurs, et reformulons la Règle 2 pour s’adapter à cette nouvelle situation.

• Règle 1 (variante) :
  on colorie les entiers $1,2,3,4,...$ avec trois couleurs, disons rouge, bleu et vert.

• Règle 2 :
  pour qu’un coloriage des entiers $1,2,3,\dots,N$ soit accepté, chaque triplet pythagoricien $(a,b,c)$ dont les constituants $a,b,c$ n’excèdent pas $N$ doit être mixte, c’est-à-dire comporter au moins deux couleurs distinctes.

La Règle 3 définissant le score $N$ d’une session du jeu reste identique.

En suivant une stratégie particulière [10], Virginie Marion-Poty, Denis Robillard et vos serviteurs ont obtenu en 2016 le score de $4632$ à ce nouveau jeu.

La stratégie employée impose des contraintes supplémentaires sur les coloriages considérés. On a pu établir que le score ainsi atteint de $4632$ est maximal dans ce cadre restreint. Voici une image du coloriage obtenu.

Un coloriage à deux couleurs étant un cas particulier de coloriage à trois couleurs, les scores obtenus avec la règle originale restent valides.

Comme pour le cas de deux couleurs, on peut se demander si un score maximal existe. Si tel est le cas, alors il doit certainement être largement supérieur à $7824$ — et même à $11066$, comme justifié ci-dessous.

Voici le tableau actuel des scores de notre variante de jeu à trois couleurs.

Rubrique oblige, terminons par une conjecture, bien naturelle au vu du cas de deux couleurs. Combien de temps celle-ci restera-t-elle ouverte ? Sans doute un grand nombre d’années, dont on souhaite seulement qu’il ne tende pas vers l’infini.

Conjecture. Il existe aussi un score maximal pour la variante à trois couleurs du jeu des triplets pythagoriciens.

Avis aux amateurs !