Donnons-nous un damier, d’une forme quelconque, et une collection de dominos. La question qui va nous intéresser ici est la suivante : est-il possible de recouvrir le damier par les dominos ? Ici, nous demandons à ce que notre recouvrement soit tel que deux dominos ne se chevauchent jamais. On parle alors de « pavage » du damier. Un exemple de pavage d’un damier est :

Bien sûr, une manière de résoudre un tel problème serait de demander à un ordinateur d’essayer toutes les possibilités, puis de nous dire si finalement un pavage est possible. Seulement cette solution n’est pas très amusante, ou plutôt, dans le jargon plus sobre des mathématiciens, elle n’est pas « satisfaisante ». Et pour cause, ce qui est intéressant, ce n’est pas tant de connaître la réponse au problème, mais de trouver un cheminement élégant qui va mener à une compréhension profonde du problème et de sa solution. Par ailleurs, cet intérêt pour une solution éclairante ne sert pas uniquement à l’auto-satisfaction du mathématicien. Typiquement, on s’attend à ce qu’une telle solution prenne la forme d’une caractérisation complète des damiers pouvant être pavés par certains dominos, c’est-à-dire d’une courte liste de conditions à vérifier permettant de dire si oui ou non un damier peut être pavé. En particulier, un ordinateur pourra résoudre un problème de pavage de manière bien plus efficace qu’en testant une à une les configurations possibles, c’est-à-dire plus rapidement et avec moins de mémoire de nécessaire. Ce qui est d’un intérêt non négligeable si l’on s’intéresse à des damiers de plusieurs millions ou milliards de cases !

Malgré son air bon enfant, ce problème de pavage s’avère très ardu. Les mathématiciens ont rivalisé d’ingéniosité pour répondre à ce genre de question, et ce sera l’occasion pour nous de rencontrer une notion importante des mathématiques contemporaines : les semi-groupes. Mais ne brûlons pas les étapes, et gardons cela pour un peu plus tard.

Quelques petits exemples

Commençons notre exploration du problème de pavage par un exemple simple, disons un damier rectangulaire $m \times n$ que l’on souhaiterait paver avec un domino $1 \times 2$. Ici, on s’aperçoit que dans de nombreux cas un pavage est possible. En fait, il n’est pas difficile de trouver un pavage lorsque $n$ ou $m$ est pair :

Mais que dire lorsque ni $n$ ni $m$ ne sont pairs ? Sur de petits exemples, on peut se convaincre qu’un pavage n’est pas possible. Le lecteur pourra tester sa sagacité sur les damiers $3 \times 3$ et $3 \times 5$. Mais comment le prouver dans le cas général ? C’est une situation très répandue en mathématiques : il est souvent bien plus difficile de démontrer que quelque chose n’est pas possible plutôt que l’inverse. Ici, notre exemple reste relativement simple, donc nous allons pouvoir nous en sortir. En effet, une observation clef est que, si un pavage est possible, alors le nombre de cases du damier doit coïncider avec le nombre de dominos fois deux. Autrement dit, le nombre de cases du damier doit être pair ! Mais, si ni $n$ ni $m$ ne sont pairs, alors le damier $m \times n$ contient un nombre impair de cases, de sorte qu’un pavage est en effet impossible dans ce cas.

Un damier rectangulaire de taille $m \times n$ est pavable par un domino $1 \times 2$ exactement lorsque $m$ et $n$ ne sont pas tous les deux impairs.

Corsons un peu l’exemple en enlevant deux cases dans deux coins opposés du damier, et posons-nous la même question : un pavage par le domino $1 \times 2$ est-il possible ? Nous savons déjà que, si un pavage est possible, alors le nombre de cases $mn-2$ doit être pair. Autrement dit, $m$ ou $n$ doit être pair. Et ensuite ? Si $m$ est pair et $n$ impair, on peut construire un pavage à la main :

Et si $m$ et $n$ sont tous les deux pairs ? Là nous allons ruser. Nous allons colorier les cases du damier de la même manière qu’un damier traditionnel :

Une observation clef est alors qu’un domino va toujours recouvrir une case noire et une case blanche. Par conséquent, si un pavage est possible, alors le nombre de cases noires et le nombre de cases blanches doivent tous les deux coïncider avec le nombre de dominos du pavage. Pourtant, si $m$ et $n$ sont tous les deux pairs, les deux coins manquants de notre damier correspondent à deux cases de la même couleur (ici noire) dans le damier traditionnel, de sorte notre damier a deux cases noires en moins par rapport au nombre de cases blanches. Ceci prouve qu’un pavage est impossible.

Le damier obtenu à partir du damier rectangulaire de taille $m \times n$ en enlevant deux cases dans deux coins opposés peut être pavé par un domino $1 \times 2$ exactement lorsque parmi $m$ et $n$ l’un est pair et l’autre impair.

Vers une méthode générale : première illustration

Nous commençons à voir que l’impossibilité de paver un damier peut être délicate à démontrer. J’aimerais maintenant illustrer une méthode qui permet (parfois) de démontrer que des pavages sont impossibles. Pour cela, considérons un damier rectangulaire auquel nous enlevons une case d’un coin et demandons-nous s’il peut être pavé par un domino $1 \times 3$.

Le point de départ va être de supposer qu’un tel pavage existe puis d’étiqueter le bord de tous les dominos par les lettres $v$ (pour vertical) et $h$ (pour horizontal) :

Considérons maintenant la suite des chemins suivants :

Ici, nous débutons avec un chemin qui part du point en bas à gauche, qui arrive au point en haut à droite, et qui longe le bord du damier par la gauche. À chaque étape, nous remplaçons une partie du chemin qui longe le bord d’un domino par la gauche par le chemin qui longe le même domino mais par la droite. Jusqu’à arriver à un chemin qui part du point en bas à gauche, qui arrive au point en haut à droite, mais cette fois qui longe le bord du damier par la droite.

À chacun de ces chemins correspond naturellement la suite des $v$ et des $h$ rencontrés en parcourant ledit chemin depuis le coin en bas à gauche jusqu’au coin en haut à droite. Nous dirons que cette suite est un « mot » écrit avec les lettres $v$ et $h$. En lisant les mots sur notre suite de chemins, nous obtenons alors la suite de mots suivante :
\[vvvv hhhh \to vhvvvhhh \to vhvvhhhv \to vhvhhhvv \to vhhhhvvv \to hvhvvv.\]
Regardons d’un peu plus près comment passer d’un mot au suivant. À la première étape, nous avons :

Autrement dit, nous avons remplacé un mot $vvvh$ par un mot $hvvv$ dans $vvvvhhhh$. De manière similaire, le troisième mot $vhvvhhhv$ est obtenu à partir du deuxième $vhvvvhhh$ en replaçant un mot $vhhh$ par un mot $hvvv$. Ces « relations de remplacement » correspondent à la forme des dominos $1 \times 3$ et $3 \times 1$ que nous utilisons pour paver le damier :

Nous venons donc de démontrer la chose suivante.

Si un pavage de notre damier par le domino $1 \times 3$ est possible, alors le mot $vvvvhhhh$, obtenu en lisant une moitié du bord du damier, peut être transformé en le mot $hhhvhvvv$, obtenu en lisant l’autre moitié du bord du damier, en appliquant des remplacements $vvvh \leftrightarrows hvvv$ et $vhhh \leftrightarrows hhhv$.

De manière analogue, si nous regardons un damier de taille $m \times n$ auquel nous avons enlevé une case dans le coin en bas à droite, nous obtenons que, si un pavage par le domino $1 \times 3$ est possible, alors nous pouvons transformer le mot
\[\underset{n \ \text{fois}}{\underbrace{v \cdots v} } \ \underset{m \ \text{fois}}{\underbrace{h \cdots h} } = v^n h^m\]
en le mot
\[\underset{m-1 \ \text{fois}}{\underbrace{h \cdots h} } ~ vh ~ \underset{n-1 \ \text{fois}}{\underbrace{v \cdots v} } = h^{m-1}vhv^{n-1}\]
grâce aux règles de remplacement $v^3h \leftrightarrows hv^3$ et $vh^3 \leftrightarrows h^3v$. Nous voudrions maintenant être capable d’utiliser cette observation afin de démontrer que certains pavages sont impossibles. Disons, pour fixer les choses, que nous souhaiterions montrer qu’un pavage est impossible si $m=5$ et $n=8$. Autrement dit, nous souhaiterions prouver que le mot $h^4vhv^7$ ne peut pas être obtenu à partir du mot $v^8h^5$ en utilisant les remplacements $v^3h \leftrightarrows hv^3$ et $vh^3 \leftrightarrows h^3v$.

Mais comment faire ? L’astuce va être de donner une nouvelle interprétation aux mots écrits avec les lettres $v$ et $h$.

Moralement, ce que nous allons faire, c’est inventer un nouveau langage à partir d’un alphabet à deux lettres $v$ et $h$, de sorte qu’appliquer un remplacement $v^3h \leftrightarrows hv^3$ ou $vh^3 \leftrightarrows h^3v$ à un mot ne change pas sa signification (créant donc un synonyme). Dès lors, si les mots $h^4vhv^7$ et $v^8h^5$ ont dans notre nouveau langage des sens différents, cela veut dire qu’il est impossible de transformer le premier en le deuxième par nos règles de remplacement.

Soyons plus précis. Ce que nous allons faire, c’est interpréter $v$ et $h$ comme des transformations. Étant donné un ensemble d’objets $E$, une transformation est un objet mathématique, une « machine » si l’on préfère, qui à chaque élément de $E$ va associer un nouvel élément de $E$. Par exemple, associer à chaque entier son double définit une transformation $a$ de l’ensemble des entiers, et additionner $1$ à chaque entier définit une transformation $b$ de l’ensemble des entiers. Maintenant, un mot écrit avec les lettres $a$ et $b$ peut naturellement s’interpréter comme une transformation. Par exemple, $abbab$ va correspondre à prendre un entier, lui appliquer $b$, puis $a$, puis deux fois $b$, puis à nouveau $a$. (Insistons sur le fait que nous sommes en train de lire le mot $abbab$ de droite à gauche !) En faisant le calcul, la transformation $abbab$ associe à chaque entier $n$ l’entier $4n+8$.

Ce que nous voulons donc faire, c’est trouver deux transformations $v$ et $h$ de sorte :

• que les transformations $v^3h$ et $h^3v$ soient identiques ;
• de même, que les transformations $vh^3$ et $hv^3$ soient identiques ;
• mais que les transformations $h^4vhv^7$ et $v^8h^5$ soient différentes.

La gageure sera alors de trouver, parmi l’infinité des possibilités, une interprétation qui sera particulièrement simple à exploiter. Il n’y a généralement pas de méthode pour cela, et il faudra davantage compter sur son intuition et son expérience.

L’interprétation que nous allons donner à $v$ et $h$ est la suivante. Posons
\[v : \left\{ \begin{array}{l} \text{à } 1 \text{ associe } 2 \\ \text{à } 2 \text{ associe } 3\\ \text{à } 3\text{ associe } 1 \\ \text{à } 4 \text{ associe } 4 \end{array} \right. \ \text{et} \ h : \left\{ \begin{array}{l} \text{à } 1 \text{ associe } 1 \\ \text{à } 2 \text{ associe } 3 \\ \text{à } 3 \text{ associe } 4 \\ \text{à } 4 \text{ associe } 2 \end{array} \right..\]
Autrement dit, $v$ et $h$ sont des transformations de l’ensemble des entiers compris entre $1$ et $4$.

Remarquons que notre choix (avisé) des transformations $v$ et $h$ rend les transformations $v^3$ et $h^3$ particulièrement simples : elles envoient chaque entier sur lui-même. Dès lors, les transformations $v^3h$ et $hv^3$ sont toutes les deux identiques à la transformation $h$ ; de même, les transformations $h^3v$ et $vh^3$ sont toutes les deux identiques à la transformation $v$. Très bien. Il reste maintenant à vérifier que les transformations $v^8h^5$ et $h^4vhv^7$ sont différentes. En calculant, on trouve que
\[v^8h^5 : \left\{ \begin{array}{l} \text{à } 1 \text{ associe } 3 \\ \text{à } 2 \text{ associe } 4 \\ \text{à } 3 \text{ associe } 1 \\ \text{à } 4 \text{ associe } 2 \end{array} \right. \ \text{et} \ h^4vhv^7 : \left\{ \begin{array}{l} \text{à } 1 \text{ associe }1 \\ \text{à } 2 \text{ associe } 2 \\ \text{à } 3 \text{ associe } 3 \\ \text{à } 4 \text{ associe } 4 \end{array} \right. ;\]
qui ce sont bien deux transformations différentes. À vrai dire, nous n’avions pas besoin de décrire $v^8h^5$ et $h^4vhv^7$ avec autant de détails. Afin de montrer que ce sont des transformations différentes, il suffit de vérifier qu’elles associent deux nombres différents à un même nombre. Par exemple, $v^8h^5$ associe $3$ à $1$ alors que $h^4vhv^7$ associe $1$ à $1$. Et il n’en faut pas plus pour conclure que $v^8h^5$ et $h^4vhv^7$ sont bien des transformations différentes.

Nous avons fini ! Paver un damier $5 \times 8$ auquel on enlève une case d’un coin par un domino $1 \times 3$ est impossible.

Mais l’argument a été plutôt long, alors reprenons-en les grandes lignes pour bien voir ce que nous avons fait.

1. Imaginons qu’il soit possible de paver notre damier par le domino $1 \times 3$. Alors il existe une suite de chemins dans le damier comme indiqué plus haut.
2. En étiquetant les côtés des dominos du pavage par les lettres $v$ et $h$, on obtient une suite de mots partant de $v^8h^5$, se terminant par $h^4vhv^7$, et telle que chaque mot est obtenu à partir du précédent en appliquant un remplacement $v^3h \leftrightarrows hv^3$ ou $vh^3 \leftrightarrows h^3v$.
3. On interprète les mots en $v$ et $h$ comme des transformations, de sorte qu’appliquer un remplacement $v^3h \leftrightarrows hv^3$ ou $vh^3 \leftrightarrows h^3v$ ne change pas la transformation représentant un mot. En particulier, les transformations représentant $v^8h^5$ et $h^4vhv^7$ doivent être identiques.
4. Pourtant, en faisant le calcul, on s’aperçoit que les transformations représentant $v^8h^5$ et $h^4vhv^7$ sont différentes. Cela prouve que le pavage n’était en fait pas possible.

Notre argument marche d’ailleurs exactement de la même manière pour les damiers de taille $(3p+2) \times (3q+2)$ où $p$ et $q$ sont des entiers, si bien que l’on obtient :

Un damier obtenu en enlevant une case dans un coin d’un damier rectangulaire de taille $m \times n$ peut être pavé par le domino $1 \times 3$ exactement lorsque $m=3p+1$ et $n=3q+1$ pour certains entiers $p$ et $q$.

Deuxième illustration

L’intérêt du raisonnement que nous venons de décrire est qu’il s’applique à toute sorte de damiers.

Prenons un damier un peu quelconque, et demandons-nous s’il peut être pavé par le domino $1 \times 2$. Par exemple,

Eh bien notre méthode permet de montrer simplement qu’un tel pavage n’est pas possible.

En effet, si un pavage était possible, alors nous pourrions transformer le mot
\[v^2h^2v^3hv^2h^4vh^5\]
en le mot
\[h^3vhv^2h^3vh^2v^2h^2vhv\]
grâce aux règles de remplacements $v^2h \leftrightarrows hv^2$ et $h^2v \leftrightarrows vh^2$.

Maintenant, interprétons les lettres $h$ et $v$ comme les transformations suivantes :
\[\begin{array}{l} v : \text {à un nombre } x \text { associe } -x \\ \\ h : \text{ à un nombre } x \text { associe } 1-x \end{array}\]
Ce sont des transformations de l’ensemble des nombres (pas nécessairement entiers). On remarquera que
\[\begin{array}{l} v^2 : \text {à un nombre } x \text { associe } -(-x)=x \\ \\ \ h^2 : \text{à un nombre } x \text{ associe } 1-(1-x)=x, \end{array}\]
c’est-à-dire que les transformations $v^2$ et $h^2$ associent chaque nombre à lui-même. Il s’ensuit que les transformations $h^2v$ et $vh^2$ sont toutes les deux identiques à $v$ ; et de même, les transformations $v^2h$ et $hv^2$ sont toutes les deux identiques à $h$.

Ainsi, appliquer un remplacement $v^2h \leftrightarrows hv^2$ ou $h^2v \leftrightarrows vh^2$ à un mot ne modifie pas la transformation le représentant, d’où on déduit que nos deux mots
\[v^2h^2v^3hv^2h^4vh^5\]
et
\[h^3vhv^2h^3vh^2v^2h^2vhv\]
doivent représenter la même transformation.

Pourtant, en faisant le calcul, on trouve que la première transformation associe à chaque nombre $x$ le nombre $x-2$, alors que la seconde transformation associe à chaque nombre $x$ le nombre $x+2$.

La conclusion est que notre pavage est en effet impossible.

Avons-nous résolu le problème complètement ?

Une question naturelle que l’on peut se poser maintenant est de savoir si la méthode que nous avons décrite ici fonctionne systématiquement. Autrement dit, si le pavage est impossible, la méthode nous le dira-t-elle toujours ? Malheureusement, non...

Considérons le problème de pavage suivant :

Il est clair qu’un tel pavage est impossible, et pour cause, aucun des deux dominos ne rentre sur le damier ! Regardons maintenant ce que dit notre méthode.

Nous souhaitons savoir si le mot $h^3v^3$ peut être obtenu à partir du mot $vh^2v^2h$ en appliquant les règles de remplacement $v^2h^2 \leftrightarrows h^2v^2$ et $v^3h^3 \leftrightarrows h^3v^3$. Et bien il se trouve que c’est possible :
\[v \ h^2 v^2 \ h \to v \ v^2h^2 \ h = v^3h^3 \to h^3v^3.\]
Ainsi, notre méthode fournit une condition nécessaire pour qu’un pavage soit possible, mais il se peut qu’elle ne soit pas suffisante.

C’est un peu décevant, mais l’idée centrale de la méthode n’en reste pas moins élégante et extrêmement féconde. Il est en effet possible d’adapter le raisonnement à des damiers « troués », ou encore de changer la géométrie des dominos, par exemple en regardant des pavages par des triangles ou bien des hexagones. Nous renvoyons le lecteur intéressé (et motivé) aux articles [1], [2], [3] et [4] (dont la lecture requiert une formation universitaire en mathématiques).

Que venons-nous de faire exactement ?

D’une certaine manière, nous avons rendu notre problème de pavage algébrique, c’est-à-dire que nous avons transféré un problème sur le pavage d’un damier par des dominos en un nouveau problème sur un objet algébrique. En l’occurrence, notre objet algébrique est un semi-groupe de transformations.

Un semi-groupe de transformations est une collection $S$ de transformations d’un ensemble $E$ telle que, si $f$ et $g$ sont des transformations qui appartiennent à notre collection $S$, alors il en est de même pour $fg$.

En effet, dans les résolutions précédentes, nous avons défini deux transformations $v$ et $h$, puis nous avons considéré l’ensemble des transformations associées à des mots en $v$ et $h$. Cet ensemble est un semi-groupe de transformations.

Cette réduction algébrique est une astuce très courante et très prolifique en mathématiques : on transfère un problème donné d’une région des mathématiques vers une autre, où de nouveaux outils seront à notre disposition pour nous aider. Cette stratégie est notamment au cœur de l’impossibilité de certaines constructions géométriques recherchées depuis l’antiquité, telles que la quadrature du cercle ou la trisection de l’angle, ainsi que de l’impossibilité de la résolution de toutes les équations polynomiales de degré cinq par radicaux (application centrale de la théorie de Galois).