CultureMath

Vous pouvez retrouver cette question au format pdf.

Question du jeudi #63 : Solomon Golomb s'est éteint le 1^er mai 2016. Il était une figure importante du lien entre recherche mathématique et mathématiques récréatives. Il est notamment l'inventeur d'un système de compression sans perte.

Du côté des mathématiques récréatives, son nom est surtout attaché au concept de polyominos, figures obtenues en assemblant des carrés de même taille. On a ainsi

• un monomino :
  
  
• un domino :
  
• deux triominos :
  
• cinq tétrominos :
  
• etc.

L'ouvrage Polyominoes: Puzzles, Patterns, Problems, and Packings de Golomb, publié par la prestigieuse Princeton University Press est en quelque sorte l'acte de naissance d'une théorie organisée des polyominos (même si le concept est évidemment beaucoup plus ancien et que le premier article de Golomb sur la question, Checker Boards and Polyominoes, date de 1954). Selon The Aperiodical, la traduction russe de ce livre inspira Alexeï Pajitnov, le créateur du mythique jeu vidéo Tetris.

On s'intéresse aujourd'hui à une question analysée par l'article fondateur de 1954, celle du pavage d'un échiquier $8 \times 8$ par des triominos. Comme $64$ n'est pas un multiple de $3$, il n'est pas possible de paver complètement un échiquier par des triominos. Mais $63$ est un multiple de $3$, ce qui rend naturelles les questions suivantes :

1. On pose un monomino sur une des cases d'un échiquier $8\times 8$. Peut-on paver les $63$ cases restantes par 21 triominos « coudés » ?
2. Même question avec $21$ triominos « droits ».

Un pavage par des polyominos est une manière de placer les polyominos, de manière à ce qu'ils recouvrent chaque case de l'échiquier, sans se superposer. Voici par exemple un pavage de l'échiquier $8 \times 8$ par les 12 pentominos et le tétromino carré.

La réponse à nos questions peut a priori dépendre de la case sur laquelle est d'abord posée le monomino.

1. Quelle que soit la case sur laquelle on pose le monomino, le reste de l'échiquier est toujours pavable par $21$ triominos coudés. En fait, on va démontrer par récurrence que si l'on pose un monomino sur un échiquier de taille $2^n \times 2^n$, on peut toujours paver le reste de l'échiquier par des triominos coudés.
   • Le cas $n = 1$ est facile : le monomino a forcément été posé sur un coin, et le reste de l'échiquier forme naturellement un triomino coudé.
     
   • Supposons le cas de l'échiquier $2^n\times 2^n$ démontré, et posons un monomino sur un échiquier $2^{n+1}\times 2^{n+1}$. On peut découper le grand échiquier en quatre parties de taille $2^n \times 2^n$, dont une seule contient le monomino.
     
     
     On peut alors poser au centre de l'échiquier un triomino coudé qui chevauche les trois autres sous-échiquiers.
     
     
     On se retrouve donc avec quatre échiquiers de taille $2^n \times 2^n$ sur chacun desquels une case est déjà occupée. D'après l'hypothèse de récurrence, on peut donc placer des triominos coudés sur chacun des ces sous-échiquiers. On obtient ainsi un pavage du grand échiquier, ce qui conclut la preuve par récurrence.
   La preuve par récurrence donne en fait une méthode algorithmique pour paver l'échiquier, où que soit posé le monomino. Voici un exemple de résultat.
   
2. On va voir que pour la plupart des cases sur lesquelles on peut poser le monomino, il est ensuite impossible de paver le reste avec des triominos droits. Commençons par recolorier l'échiquier, avec trois couleurs (bleu, vert et rouge), de façon alternée.
   
   
   Si l'on pose sur un tel échiquier un triomino droit, les trois cases du triomino seront sur trois cases de couleurs différentes. Or, contrairement au coloriage classique de l'échiquier, les trois couleurs ne sont pas représentées équitablement sur l'échiquier (ce serait impossible, puisque $3$ ne divise pas $64$). Plus précisément, il y a $21$ cases bleues et rouges, et $22$ cases vertes.
   
   Pour que l'on puisse paver l'échiquier avec un monomino et $21$ triominos droits, il faut donc que le monomino soit sur une case verte. Autrement dit, si le monomino est sur une des cases grisées dans le dessin suivant, le pavage sera impossible :
   
   
   Cependant, le dessin que l'on vient d'obtenir n'est pas symétrique, ce qui nous permet de dire mieux. Prenons un exemple : on vient de montrer que si l'on pose le monomino dans le coin inférieur gauche, on ne pourra pas paver le reste. Notre argument ne marchait pas pour le coin inférieur droit, mais il est évident que si l'un est impossible, l'autre également. (Si on pouvait paver le carré par un monomino dans le coin inférieur droit et $21$ triominos, il suffirait de tourner l'échiquier d'un quart de tour pour obtenir un pavage où le monomino est dans le coin inférieur gauche, ce que l'on vient d'exclure).
   
   Plus généralement, toutes les cases qui sont envoyées par une symétrie du carré sur une case grisée sont également des cases qui ne pourront pas accueillir le monomino.
   
   Une manière équivalente d'utiliser la symétrie est de dire que l'on peut répéter l'argument de coloriage avec les coloriages obtenus en faisant subir à notre coloriage original toutes les isométries du carré possible : une case qui n'est pas verte pour tous les coloriages ainsi obtenue est une case impossible.
   
   
   Quelle que soit la manière de présenter cet argument de symétrie, on peut alors vérifier que presques toutes les cases sont maintenant exclues. Pour être plus précis, toutes les cases grisées dans le dessin suivant sont impossibles.
   
   
   Puisque les quatre cases restantes sont toutes images les unes des autres par des symétries du carré, il ne reste donc plus qu'une question à trancher : peut-on paver l'échiquier en utilisant un monomino en f7 (pour utiliser les coordonnées du jeu d'échec) et 21 triominos ?
   
   On vérifie alors aisément que c'est effectivement possible.
   
   
   En résumé, il sera possible de paver le reste de l'échiquier par des triominos droits si et seulement si le monomino est initialement posé sur une des quatre cases c3, f3, c7 ou f7.