Le jeu des échecs, avec ses règles simples régissant le déplacement des pièces sur son espace clos, a inspiré bien des problèmes ludiques. Certains de ceux-ci ont d’étonnants liens avec des domaines variés des mathématiques. Dans le dialogue entre échecs et mathématiques, ce fut parfois la recherche mathématique qui modifia les règles des échecs pour les faire concorder à des problèmes intéressants.
Un des plus célèbres problèmes mathématico-échiquéens est le Problème des 8 dames : on demande à placer 8 dames sur un échiquier 8 × 8 de sorte qu’aucune dame n’en menace une autre. Un problème similaire est le problème de Domination de l’échiquier par les dames : on y demande le nombre minimal de dames permettant que toutes les cases de l’échiquier soient « surveillées », c’est-à-dire menacées ou occupées par une dame. Ces deux problèmes sont liés. Le premier a trait au nombre maximal de dames dominant l’échiquier sans se menacer; le deuxième, au nombre minimal de dames dominant l’échiquier.
Au fil du temps, les mathématiciennes et mathématiciens étudiant ces problèmes ont aussi tenté de les généraliser et d’ajouter ou enlever des contraintes afin de mieux les comprendre. Au-de-là de la première généralisation agrandissant l’échiquier à un échiquier $n \times n$, certaines contraintes changent profondément la nature des règles. Nous verrons deux de ces tentatives : une sur le problème des $n$ dames faite par le mathématicien hongrois Georg Pólya en 1918 consistant à mettre l’échiquier, non pas sur un plan, mais sur un tore, ou un beigne; l’autre étudiée un siècle plus tard par les mathématiciennes Hannah Alpert et Érika Roldán sur le problème de domination des dames, en changeant l’échiquier pour des polyominos, des sortes de pièces de Tetris.
Le problème toroïdal des $n$ dames
Quelles conditions n doit-il respecter pour qu’il soit possible d’avoir une solution au problème des $n$ dames sur un échiquier $n × n$ toroïdal ?
Le problème de domination des polyominos
Quel est le nombre minimal de dames nécessaire pour dominer un polyomino de $N$ cases ?
Généralisation de Pólya, avec un petit détour modulaire
Considérons l’échiquier toroïdal. Comment les pièces bougent-elles sur un tel échiquier ? Il n’est pas nécessaire d’avoir avec soi un beigne quadrillé pour imaginer le mouvement, un simple échiquier plat suffit. On transforme un échiquier classique en échiquier toroïdal en éliminant les frontières : une pièce qui atteint la frontière gauche ressort par la frontière droite, et de même pour celles du haut et du bas.
Afin de nous aider à visualiser, construisons une sorte d’échiquier « modulaire » qui étend l’échiquier initial durant le mouvement des pièces en mettant plusieurs échiquiers côte à côte. Durant leur déplacement, les pièces peuvent se déplacer sur tous les échiquiers et elles retournent à la case correspondante sur l’échiquier initial à la fin.
Notons la position d’une dame par ses coordonnées cartésiennes $(c,r)$ pour $c$, la colonne et $r$, la rangée en comptant du bas vers le haut et de la gauche vers la droite. Par exemple, à la Figure 6, une dame en (6, 5) atteint la case (9, 8) sur un échiquier supplémentaire. Lorsqu’on rassemble les échiquiers, cette case devient la case (1, 8).
Arithmétique modulaire
Y a-t-il une façon plus facile de donner le mouvement d’une dame ? Bien sûr ! Le procédé décrit ci-haut est un exemple d’arithmétique modulaire. Dans le monde modulaire, les égalités sont remplacées par des congruences liées à un nombre $n$. Deux nombres $a,b$ sont dits congrus modulo $n$ si les deux ont le même reste après division par $n$, autrement dit si $a=k \times n + b$ pour un certain nombre entier $k$; on note alors $a=b \mod n$.
Les heures sont un système modulaire pour $n =24$ (ou $n=12$). Quand on dort 8 heures après un coucher à 23h, on se réveille à 7h, et non pas à 31h. Sans le savoir, on fait la congruence 31 = 7 mod 24.
L’échiquier « modulaire » que nous avons introduit est un exemple d’arithmétique modulaire pour $n = 8$. Tous les échiquiers supplémentaires ajoutés sont issus de translations horizontales ou verticales de 8 unités de l’échiquier initial. L’opération « revenir à l’échiquier initial » revient précisément à prendre le modulo de chaque coordonnée dans la paire $(c, r)$ donnant la position d’une pièce.
Le problème de Pólya
La grande différence du problème toroïdal des $n$ dames avec le problème classique survient sur les diagonales. Par exemple, dans un échiquier classique $8 \times 8$, il y en a 15 de chaque sorte (Nord-Ouest et Sud-Est); sur un échiquier toroïdal, il n’y en a plus que 8 (voir Figure 7).
Il est connu que tous les échiquiers normaux $n \times n$ admettent une solution au problème des $n$ dames dès que $n \geq 4$. Pólya se demandait s’il y a toujours une solution au problème des n dames sur un échiquier toroïdal.
Avant de donner la réponse complète de Pólya, étudions le problème pour un échiquier $8 \times 8$.
Numérotons les 8 diagonales SE comme à la Figure 7. Écrivons, pour chaque case de l’échiquier, sa colonne $c_i$, sa rangée $r_i$ et sa diagonale SE $d_i$; chacun de ces nombres est compris entre 1 et 8. Remarquons que le choix de numérotation des diagonales fait en sorte que $c_i + r_i + d_i$ est toujours divisible par 8 (Figure 8). Supposons qu’il y ait une solution. Les huit dames seraient sur huit colonnes distinctes, huit rangées distinctes et huit diagonales SE distinctes. Additionnons les sommes des colonnes, des rangées et des diagonales SE :
\[\begin{array}{r c l}\displaystyle \sum_{i=1}^8 (c_i +r_i +d_i)&=& \displaystyle \sum_{i=1}^8 c_i + \displaystyle \sum_{i=1}^8 r_i + \displaystyle \sum_{i=1}^8 d_i \\&=& 3 \displaystyle \sum_{i=1}^8 i = 3 \times 36 =108. \end{array} \]
Mais, il y a un souci : 108 n’est pas divisible par 8. Donc notre supposition est impossible et il ne peut pas y avoir de solution pour l’échiquier $8 \times 8$.
La contrainte de Pólya est donc non triviale. Est-elle trop restrictive cependant ? En vérifiant les petits $n$, on peut rapidement vérifier que non : l’échiquier $5 \times 5$ admet une solution toroïdale. On l’obtient en plaçant une dame à chaque bond de cavalier (voir Figure 9).
Qu’est-ce que l’échiquier $5 \times 5$ a que l’échiquier $8 \times 8$ n’a pas ? Pólya donne un critère élégant pour déterminer la possibilité ou l’impossibilité du problème.
Théorème (Pólya 1918)
Soit $n \geq 4$. Une solution au problème des $n$ dames sur un échiquier toroïdal $n \times n$ est possible si et seulement si $n$ et 6 sont relativement premiers, c’est-à-dire si 2 et 3 ne divisent pas $n$.
Pour prouver le théorème, Pólya montre d’abord que la méthode des bonds de cavalier que nous avons présentée fonctionne quand $n$ et 6 sont relativement premiers. Ensuite, il montre qu’il est impossible que 2 ou 3 divisent n s’il existe une solution, en manipulant des sommes sur les éléments de ces listes. Ces manipulations suivent la même idée que la démarche présentée plus haut pour l’échiquier $8 \times 8$, mais utilisent l’arithmétique modulaire pour la généraliser.
Par exemple, déterminer si deux dames $(c_i, r_i)$ et $(c_k, r_k)$ partagent la même diagonale sur un échiquier $n \times n$ revient à vérifier une congruence : elles sont sur une même diagonale SE si $r_i +c_i =r_k+c_k \mod n$ et sur la même diagonale NE si $r_i -c_i =r_k–c_k \mod n$. En effet, elles seraient alors respectivement sur la même droite modulaire de pente -1 et de pente 1.
Pour illustrer, prenons la position de la Figure 10. Bien que cette position fonctionne sur un échiquier $8 \times 8$ normal, elle n’est pas une solution sur l’échiquier toroïdal. En effet, les dames (1, 6) et (6, 3) sont sur la même diagonale NE, car $6-1=5=-3=3-6 \mod 8$, et les dames (4, 2) et (7, 7) sont sur la même diagonale SE puisque $4+2=6=14=7+7 \mod 8$.
La preuve du théorème de Pólya
Fixons tout d’abord une notation. Une position de dame avec une dame sur chaque colonne est notée par une liste $(r_1,\ldots,r_n )$. C’est une solution si et seulement si :
I. la liste $(r_1,…,r_n )$ contient tous les nombres de 1 à $n$, on dit donc que c’est une permutation;
II. la liste $((r_1 + 1)\mod n, …, (r_n + n)\mod n)$ est une permutation (avec $0 = n \mod n)$;
III. la liste $((r_1–1)\mod n, …, (r_n-n)\mod n)$ est une permutation (avec $0 = n \mod n)$.
Démonstration
Supposons que 2 et 3 ne divisent pas $n$. Une solution est donnée en faisant des bonds de cavalier. Soit la liste $(r_1,r_2, …, r_n )$ où $r_k=2k \mod n$; pour l’échiquier $5 \times 5$, par exemple, cela donne (2, 4, 1, 3, 5). Nous allons nous assurer que les points I-II-III sont vérifiés.
Le point I est vérifié comme 2 ne divise pas $n$ et que 2 est premier. En arithmétique modulaire, cela veut dire que 2 est inversible modulo $n$ (par exemple $2^{–1}=3 \mod n$ pour $n=5$, car $3 \times 2=6=1 \mod 5$. Cela veut dire que la liste $(2k \mod n)$ est une permutation. En effet si $2k=2p \mod n$, on peut multiplier par l’inverse et alors $2^{–1} \times 2k = 2^{–1} \times 2p \mod n$, ce qui revient à $k = p \mod n$. Ceci prouve que tous les $r_i=2i$ sont distincts modulo $n$.
De même, pour le point II, remarquons que la somme donne $(3, 6, …, 3n) \mod n$. Comme 3 ne divise pas $n$ et qu’il est premier, 3 est inversible modulo $n$, et donc la liste est aussi une permutation.
Le point III se vérifie en remarquant que la différence des deux permutations est $2k-k=k \mod n$, donc le résultat est simplement la permutation $(1,2,…,n)$. Les trois points sont vérifiés : nous avons construit une solution.
Pour prouver l’autre direction du théorème, donc qu’une solution nécessite que n ne soit pas divisible par 2 ou 3, supposons que nous ayons une solution (r_1,…,r_n). Elle respecte alors les points I-II-III. Le point III indique que
\[((r_1–1)\mod n,(r_2–2)\mod n,…,(r_n–n)\mod n)\]
est une permutation. Donc, additionner ses éléments revient à additionner tous les nombres de 1 à $n$ après un réarrangement des termes. On obtient donc la formule bien connue pour la somme de $n$ nombres consécutifs :
\[\displaystyle \sum_{j=1}^n (r_j-j)= \sum_{k=1}^n k = \frac{n(n+1)}{2}\mod n.\]
On peut calculer la somme autrement en la séparant. Comme $(r_1, …, r_n)$ est une permutation par le point I, elle contient aussi tous les nombres de 1 à $n$, et donc la différence est :
\[\displaystyle \sum_{j=1}^n (r_j-j)= \sum_{j=1}^n r_j- \sum_{j=1}^n j = 0\mod n.\]
En combinant les deux égalités nous avons $n(n+1)/2=0 \mod n$. Cela veut dire que $n$ divise $n(n+1)/2$. Si $n$ était pair, alors $n=2^sr$ avec $r$ impair et alors $n(n+1)⁄2=2^{s-1}(2^s+r)$. Or, comme ce nombre n’a que $s–1$ facteurs 2, il ne peut pas être divisible par $n$. Ceci implique que $n$ est impair.
Pour montrer que 3 ne divise pas $n$, commençons par additionner le carré des éléments des deux listes $((r_1 + 1)\mod n, …, (r_n + n)\mod n)$ et $((r_1 – 1)mod n, …, (r_n – n)\mod n)$.
Comme chaque liste est une permutation par les points II et III, la somme des carrés de ses éléments après réarrangement est la somme des carrés de 1 à $n$. On additionne ensuite les deux sommes en utilisant la formule de sommation des carrés, ce qui donne :
\[\displaystyle \sum_{j=1}^n (r_j-j)^2 + \sum_{j=1}^n (r_j+j)^2 = 2\sum_{j=1}^n j^2 \\ = 2 \frac{n(n +1)(2n +1)}{6} \mod n.\]
Additionnons cette fois-ci en développant les deux carrés ce qui donne, comme $(r_1,…,r_n)$ est une permutation par le point I,
\[\displaystyle \sum_{j=1}^n (r_j-j)^2= \sum_{j=1}^n (r_j+j)^2\]
\[\displaystyle = \sum_{j=1}^n (r_{j}^{2}-2r_j+j^2)= \sum_{j=1}^n r_{j}^{2}-2r_j+j^2)\]
\[\displaystyle = 4 \sum_{j=1}^n = \frac{2n(n+1)(2n+1)}{3} \mod n.\]
Et donc l’égalité suivante est obtenue :
\[\frac{n(n +1)(2n +1)}{3}= \frac{2n(n +1)(2n +1)}{3} \mod n,\]
qui se simplifie en $n/3=2n/3 \mod n$. Cette équation n’est possible que si 3 ne divise pas $n$. En effet, si 3 divise $n$, alors $n=3^sr$ pour un $r$ non-divisible par 3 et l’équation demande que $n⁄3=3^{(s-1)}r$ soit divisible par $n$, une contradiction.
Finalement, il y a une solution si et seulement si $n$ et 6 sont relativement premiers. Nous avons donc prouvé le théorème de Pólya.
Polyominos et le problème de domination
Tournons-nous maintenant vers une seconde généralisation de l’échiquier : les polyominos. Dans notre usage, un polyomino sera un ensemble connexe quelconque de cases collées les unes aux autres. Un échiquier ne sera donc plus une grille carrée, mais n’importe quel agencement de cases avec pour seule contrainte à notre fantaisie, l’adjectif « connexe » utilisé ci-haut, qui demande que toutes les cases soient reliées les unes aux autres par un chemin formé de cases appartenant au polyomino. Voici deux polyominos et un non-polyomino:
Comme notre échiquier n’est maintenant plus une grille $n \times n$, on ne peut plus attribuer de sens au problème des $n$ dames : quel $n$ faudrait-il considérer ? On se tourne donc vers un problème plus général, dit « de domination », qui s’énonce de la façon suivante : étant donné un polyomino formé de $N$ cases, combien faut-il placer de dames pour surveiller toutes les cases ? Si un certain ensemble de dames placées à certaines cases du polyomino surveille toutes les cases, on dit que cet ensemble « domine » le polyomino.
Remarquons d’abord qu’une contrainte a disparu par rapport aux problèmes précédents : les dames peuvent maintenant se menacer entre elles. Cette remarque nous indique alors une première solution : on n’a qu’à placer une dame sur chaque case du polyomino! Ceci fonctionne, mais n’est pas très intéressant. On cherchera donc plutôt le nombre minimal de dames nécessaire pour dominer un échiquier polyominal. Cette question dépend évidemment de la forme du polyomino. Par exemple, la domination des polyominos de 9 cases peut nécessiter une, deux ou trois dames.
Le problème de domination correctement formulé devient alors le suivant : étant donné un échiquier polyominal à $N$ cases, quel est le plus petit nombre de dames suffisant pour le dominer, peu importe sa forme ?
La réponse à ce problème est donnée, au début de l’année 2021, par les mathématiciennes Hannah Alpert et Érika Roldán.
Théorème (Alpert-Roldán 2021)
Le nombre de dames qui est suffisant et parfois nécessaire pour dominer un polyomino à $N \geq 3$ cases est $\lfloor N/3 \rfloor$ .
Commençons par montrer que ce nombre est parfois nécessaire. Il suffit d’exhiber des exemples de polyominos à N cases qui ne peuvent pas être dominés par moins de $\lfloor N/3 \rfloor$ dames. On les construit en empilant des lignes de trois cases comme dans les dessins ci-contre, selon que $N= 0,1$ ou $2 \mod 3$.
Pour montrer que ce nombre est aussi suffisant, il nous faut introduire la notion de distance entre deux cases d’un polyomino. Cette dernière est définie comme étant la longueur du plus court chemin entre ces deux cases, où l’on se déplace d’une case à une autre à gauche, à droite, en haut ou en bas, mais pas en diagonale, et en restant toujours sur des cases appartenant au polyomino.
Alors, une dame placée sur une case d’un polyomino surveille toutes les cases qui sont à distance plus petite ou égale à 2. En effet, elle surveille évidemment sa propre case, qui est à distance 0, et toutes les cases qui sont à distance 1, car elle peut se déplacer d’une case dans toutes les directions. Les cases à distance 2 sont soit des cases directement en diagonale de sa position, auquel cas la dame les surveille, soit des cases à distance 2 en ligne droite dans une certaine direction, que la dame surveille, car elle peut se déplacer d’autant de cases qu’elle veut dans une direction donnée.
Soit maintenant un polyomino à $N$ cases. La preuve suit l’idée suivante. Choisissons une case du polyomino, qu’on appelle racine, et notons, pour chacune des cases restantes, sa distance à la racine. Colorions ensuite les cases du polyomino avec trois couleurs selon que leur distance à la racine soit congrue à 0, 1 ou 2 mod 3. Chaque case a alors une couleur et la couleur la moins représentée apparaît au plus $\lfloor N/3 \rfloor$ fois. Plaçons alors une dame sur chacune des cases de cette couleur. Pour chaque case du polyomino, en empruntant le plus court chemin vers la racine, on croisera forcément1 une dame en au plus deux pas. Par le résultat plus haut, comme cette dame se trouve à distance plus petite ou égale à deux, elle surveille la case; toutes les cases du polyominos sont donc surveillées par au moins une dame.
Conclusion
Avec un peu de créativité en mathématiques, on arrive souvent à explorer des avenues inattendues en modifiant un problème, peu importe la provenance de ce dernier. Pas besoin de plus que de se demander : et si…?
Pour en s\(\alpha\)voir plus !
- ALPERT, H. et ROLDÁN, É. Art Gallery Problem with Rook and Queen.
Vision Graphs and Combinatorics 37:2 (2021), 621–642. - Un étudiant d’Érika Roldán, Christoph Muessig, a mis en ligne un programme permettant de tester le problème de domination des tours sur des polyominos aléatoires.
https://mygame.page/art-galery-with-rooks-guards - Pour plus de problèmes mathématico-échiquéens, le livre suivant est tout désigné.
WATKINS, J.J. The mathematics of chessboard problems. Princeton University Press, 2004.
- Un potentiel problème survient pour la racine et les cases à distance 1. On pourrait, pour ces cases, ne pas croiser de dames dans le plus court chemin vers la racine. En choisissant comme racine, si possible, une case qui ne touche qu’à une seule autre case, on peut vérifier que toutes ces cases sont bel et bien surveillées par une dame. Si aucune telle case n’est présente, on peut choisir n’importe laquelle comme racine. ↩
