Que ce soit pour les résoudre ou pour montrer qu’on ne peut le faire, les puzzles permettent de mettre en action des idées fondamentales en mathématiques.
Un bel exemple est donné par le jeu des tours de Hanoï dont l’invention est attribuée à Édouard Lucas. Dans la version illustrée ici, il faut déplacer la tour de départ (image du haut), formée de huit disques empilés sur la tige de gauche, pour la placer sur la tige de droite (image du bas), en respectant les consignes suivantes :
– on ne peut déplacer plus d’un disque à la fois, d’une tige à une autre;
– on ne peut placer un disque que sur un autre disque plus grand que lui ou sur un emplacement vide.
Il y a plusieurs questions à saveur mathématique que l’on peut se poser, une fois que l’on a résolu le puzzle. Combien de déplacements doit-on faire, au minimum, pour y arriver ? S’il y avait eu une tour formée par sept disques, combien de déplacements cela prendrait-il ? Lorsque le jeu est dans la position illustrée dans l’image du milieu, combien de coups reste-il à faire ? Répondre à ces questions nous permet de mieux comprendre le jeu, et sa complexité, une fois qu’on l’a résolu. L’article de Benoît Rittaud sur les tours de Hanoï1 l’illustre fort bien.
Dans d’autres cas, l’utilisation des mathématiques peut permettre de comprendre pourquoi il est impossible de résoudre un puzzle. Cela peut sembler surprenant. Pourquoi considérer un puzzle qu’on ne peut résoudre ? Et comment être certain que la résolution est bel et bien impossible ?
Un puzzle simple et une idée fondamentale
Prenons un échiquier de 64 cases auquel on enlève les deux cases situées aux extrémités de l’une des deux diagonales. Il reste alors 62 cases. On vous donne 31 dominos rectangulaires qui couvrent chacun exactement deux cases. Le but du puzzle est de placer les 31 dominos de manière à couvrir exactement ces 62 cases. Vous pouvez essayer : vous verrez que c’est impossible. Mais sauriez-vous expliquer pourquoi cela est impossible ?
On peut remarquer que l’échiquier illustré a 32 cases noires et 30 cases blanches : comme chaque domino couvre exactement une case de chaque couleur, il restera toujours 2 cases noires une fois placés les 30 premiers dominos, et on ne peut donc pas le recouvrir entièrement. Cet énoncé coloré se prête moins bien à une généralisation que le suivant.
Attribuons les valeurs -1 et 1 en alternance aux cases de l’échiquier, en débutant avec 1 dans une des cases d’un coin, et en poursuivant de sorte que deux cases voisines horizontalement ou verticalement aient une valeur différente. Alors chaque domino couvre exactement deux cases dont la somme des valeurs est 0. Avec 31 dominos, on couvrirait donc 62 cases dont la somme des valeurs est aussi 0. Mais la somme des valeurs des 62 cases est en fait 2, et on ne peut donc pas couvrir les 62 cases.
Voyons le tout comme un jeu
Décrivons le tout comme un jeu. On a une position initiale du jeu, soit les 62 cases non recouvertes, et un coup consiste à placer un domino rectangulaire.
– En attribuant des valeurs aux cases, on peut attribuer une valeur initiale au jeu en sommant la valeur des 62 cases non recouvertes: cela donne une valeur de 2.
– Après chacun des coups, la valeur du jeu formé par les cases non recouvertes est aussi calculée : cette valeur demeure 2, peu importe de coup joué.
Jouer un coup ne change donc pas la valeur du jeu, qui ne peut donc jamais devenir nulle. On ne peut donc pas recouvrir toutes les cases du jeu.
La clé
Pour qu’une telle idée fonctionne, on doit trouver une manière d’attribuer une valeur aux différents états d’un jeu de telle sorte que les coups joués ne puissent pas permettre de passer de la valeur du jeu dans sa position initiale à la valeur du jeu dans la position finale souhaitée.
Le solitaire
Dans le jeu classique du solitaire, des billes sont placées sur un plateau comme celui illustré, et la position centrale est vide. Une bille peut « sauter » par-dessus une bille horizontalement ou verticalement pour atteindre une position vide, et la bille par-dessus laquelle on a fait le saut est retirée.
Dans le jeu illustré ici, le premier coup est donc unique, à une rotation près du plateau.
L’objectif est de retirer toute les billes sauf une, et que cette bille soit alors au centre du plateau.
Dans ce jeu, il y a bel et bien une solution! On ne révèle rien pour vous laisser le plaisir de résoudre le puzzle vous-même.
Une variante du solitaire : les soldats de Conway
Le jeu du solitaire est très connu (voir encadré). Dans la variante que nous présentons, on imagine un échiquier de taille infinie séparé en deux par un trait horizontal. Des jetons sont disposés sur la moitié inférieure (cases en gris) et les mouvements sont les mêmes que ceux du jeu de solitaire : un jeton peut sauter par-dessus un jeton qui lui est adjacent horizontalement ou verticalement (mais pas en diagonale) pour atteindre une position vide, et le jeton par-dessus lequel on a sauté est retiré. Voici un exemple sur une partie de l’échiquier qui permet de placer un jeton à la 2e rangée de la moitié du haut en 3 mouvements. (Le jeton rouge est celui qui effectue le prochain saut.)
Jusqu’où peut-on monter ?
Ici, le jeu consiste à amener des jetons aussi haut que possible. Peut-on aller à la 3e rangée ? Et à la 4e, et ainsi de suite ? Comme il y a une infinité de jetons, on serait porté à croire que l’on peut atteindre n’importe quelle rangée. Après avoir fait quelques essais, on atteint la 3e rangée, puis la 4e rangée en persévérant. Mais aller au-delà de la 4e rangée peut sembler impossible. Doit-on persévérer ?
Lorsque l’on regarde des problèmes de ce genre, on peut être porté à vouloir regarder tous les détails : on veut expliquer pourquoi certains coups sont « clairement » mieux que d’autres, et donc que si on n‘y arrive pas, c’est que c’est impossible ! Et cela devient vite très compliqué à suivre, et encore plus à vraiment bien justifier.
La clé, encore une fois !
On va montrer qu’on ne peut pas atteindre la 5e rangée. Pour ce faire, on attribue une valeur (appelée un poids) à chacune des cases de l’échiquier, et la valeur du jeu est la somme des valeurs des cases occupées par un jeton. Comme on voudra avoir la valeur du jeu dans sa position initiale, et qu’il y a une infinité de jetons, il faut bien choisir les poids. L’idée est de prendre un nombre réel a tel que \(0 < a < 1\) et d’attribuer des poids selon la méthode suivante.
On choisit une case de la 5e rangée auquel on donne la valeur 1. Elle est en jaune sur la figure. On va montrer que cette case ne peut pas être atteinte.
On attribue la valeur a à la position immédiatement en dessous, puis la valeur a2, et ainsi de suite sur la colonne contenant la position choisie. On augmente donc l’exposant de 1 à chaque fois que l’on s’éloigne de la position choisie, vers le bas.
Pour les cases qui ne sont pas dans la colonne centrale, on augmente l’exposant de 1 à chaque fois que l’on s’éloigne de la colonne centrale. On a le résultat dans la grille, que l’on imagine infinie.
La valeur de la position initiale du jeu, qui est la somme des valeurs des cases occupées au début, est
\[\displaystyle \frac{a^5+a^6}{(1-a)^2}\]
(voir encadré).
Les Sommations
\[(1 – a)(1 + a + a^2 + \cdots + a^n) = 1 – a^{n+1}, \]
on peut diviser par \((1 – a)\) des deux côtés de l’équation pour obtenir
\[1+a+a^2+\cdots+a^n) = \displaystyle \frac{1 – a^{n+1}}{1-a}.\]
On remarque alors que plus \(n\) est grand, plus \(a^{n+1}\) est près de 0, de telle sorte qu’à la limite, on aura bien
\[1+a+a^2 \cdots = \displaystyle \frac{1}{1-a}. \]
Une fois que l’on a cela, que donne la somme de tout ce qu’il y a dans le tableau ?
Si on somme les valeurs des cases dans la colonne centrale, on a
\[\begin{array}{l c l}a^5+a^6+a^7+ \cdots &=& a^5(1+a+a^2+\cdots) \\ &=& \displaystyle \frac{a^5}{1-a}.\end{array}\]
Puis, pour les deux colonnes voisines, on obtient deux fois le terme \(a^6/(1 – a).\) Et ainsi de suite, de sorte qu’on obtient finalement
\[\begin{array}{l c l}\displaystyle \frac{a^5+2a^6+2a^7+ \cdots}{1-a} & = & \displaystyle \frac{a^5+a^6+a^7+ \cdots}{1-a} + \displaystyle \frac{a^6+a^7+a^8+ \cdots}{1-a} \\ & = & \displaystyle \frac{a^5+a^6}{(1-a)^2}. \end{array} \]
Bien choisir la valeur de a
Peut-on choisir la valeur de a pour que les coups ne modifient pas la valeur du jeu ? On voit que les coups vers le haut ainsi que ceux vers l’axe central (qui contient la case de valeur 1) consistent tous à ce qu’un jeton dans une position de valeur \(a^{n+2}\) saute par-dessus un jeton dans une case de valeur \(a^{n+1}\) pour atteindre la position de valeur \(a^n\). On voudrait donc que \(a^{n+2} + a^{n+1} = a^n\) pour toute valeur positive de \(n\), ce qui sera vrai si \(a^2 + a = 1.\) Prenons donc comme valeur de a la racine positive du polynôme \(p(x) = x^2 + x – 1 = 0\) (On peut vérifier que
\[a= \displaystyle \frac{-1+ \sqrt{5}}{2}, \]
qui est bien entre 0 et 1.)
Et les autres coups possibles ?
Les autres coups possibles consistent à descendre ou à s’éloigner de l’axe central, ou encore à sauter par-dessus un jeton de l’axe central. On a alors un jeton dans une case de valeur \(a^n\) qui saute par-dessus un jeton dans une case de valeur \(a^{n+1}\) pour atteindre une case de valeur \(a^{n+2}\) ou une case de valeur \(a^n.\) Dans les deux cas, on diminue la valeur du jeu puisque \(a^n + a^{n+1} > a^{n+2}\) et \(a^n + a^{n+1} > a^n.\)
La valeur initiale du jeu est 1, et celle de la position finale souhaitée est > 1.
Avec cette valeur de \(a\), on a \(a^2 = 1 – a\) et la valeur initiale du jeu est donc
\[\displaystyle \frac{a^5+a^6}{(1-a)^2}= \frac{a^4(a+a^2)}{a^4}=a+a^2=1.\]
S’il y a un jeton à la case de poids 1, dans la 5e rangée, alors la valeur du jeu sera strictement supérieure à 1 car il y aura aussi d’autres jetons dont le poids n’est pas nul. Comme aucun coup ne permet d’augmenter la valeur du jeu, on ne peut pas en arriver à cela.
Invariant et monovariant
John Conway a lui-même résolu de cette manière la variante du jeu du solitaire qui porte son nom. Il a de fait introduit une valeur qui n’est pas invariante mais qui ne peut pas croître avec les coups joués. On parlera alors de monovariant, ici décroissant.
L’utilisation d’invariant ou de monovariant est fréquente en mathématiques. Elle peut permettre de montrer que des objets mathématiques appartiennent à des classes différentes, ou que des configurations ne peuvent être atteintes en utilisant certains processus précis, comme dans le cas que nous venons de résoudre.
- « Les tours de Hanoï », Accromath vol. 11.1, Hiver-Printemps 2016 ↩
