Les problèmes de pavage existent depuis fort longtemps et restent à ce jour l’objet de recherches intensives. Vouloir faire le tour de l’ensemble de ces problèmes étant un projet nettement trop ambitieux, on va s’intéresser essentiellement dans ce qui suit à présenter certaines problématiques et questions ouvertes nécessitant un minimum de connaissances et portant sur des polyominos. Si ce nom n’évoquera pas grand-chose à certains lecteurs, il rappellera sans doute des souvenirs à ceux ayant vécu la frénésie qui s’empara du monde du jeu vidéo à la fin des années 80 avec Tetris, qui reste à ce jour l’un des plus grands succès planétaires dans le domaine (selon Wikipedia, plus de 35 millions de ventes enregistrées en juin 2009).

Un polyomino, qu’ès aquò ?

Le constituant élémentaire (atomique diraient les physiciens) de notre sujet est le petit carré. Aussi, on suppose que l’on possède un énorme tas de petits carrés qui sont tous rigoureusement identiques.

Un polyomino est un assemblage fini de petits carrés collés entre eux, de sorte que les côtés qui sont collés l’un contre l’autre sont entièrement en contact (on peut appeler cela la règle d’assemblage). Cette dénomination a été proposée par Solomon Golomb au début des années 50 puis rapidement popularisée par Martin Gardner à travers de nombreux livres de jeux et puzzles mathématiques. On précise parfois qu’un polyomino doit être simplement connexe, ce qu’il signifie qu’il doit être sans trou. La plupart du temps, la distinction n’est pas très importante car les polyominos troués ne vérifient aucune des bonnes propriétés qui peuvent nous intéresser !

On peut choisir la convention de représenter un polyomino en utilisant un trait plein pour son bord et un trait en pointillés pour représenter les côtés qui ont été collés. On utilise des noms plus spécifiques pour les polyominos constitués d’un nombre donné de petits carrés : domino (2 petits carrés), triomino (3), tetromino (4), pentomino (5), etc. Les polyominos sont constitués d’un nombre fini de petits carrés, mais on peut aussi s’intéresser à des assemblages contenant une infinité de petits carrés, que l’on appellera surface, la plus grande surface possible étant le plan présenté sous forme de quadrillage.

Les polyominos présentent l’avantage de pouvoir être très facilement manipulés, ce qui permet une appropriation rapide d’une large variété de problèmes à destination du jeune public, par exemple à l’aide de briques colorées en plastique ayant assuré la renommée d’une célèbre firme danoise !

Beaucoup de questions portant sur les polyominos sont des problèmes d’existence (peut-on trouver un assemblage satisfaisant certaines contraintes ?) et de dénombrement (combien y a-t-il de telles possibilités ?). L’étude de ces questions relève d’un domaine appelé combinatoire. Entre autres, on peut citer parmi les questions les plus usuelles :

• Avec un nombre fixé de petits carrés, combien de polyominos différents peut-on constituer ?
• Si l’on se donne deux polyominos P1 et P2, combien doit-on utiliser de polyominos P1 pour recouvrir entièrement le polyomino P2 ? Combien peut-on placer de polyominos P1 à l’intérieur du polyomino P2 sans former de chevauchement ?

On peut fusionner certaines de ces questions en une nouvelle problématique qui correspond à un cas d’optimisation : avec des exemplaires d’un polyomino donné, peut-on paver (c’est-à-dire recouvrir sans chevauchement) un polyomino ou une surface donné(e) ?

Nous ne reviendrons que partiellement sur cette dernière question qui est vraiment difficile !

Polyominos identiques, polyominos différents

Les questions précédentes font apparaître des notions dont chacun peut se faire une idée intuitive qui demande toutefois à être précisée. Quand peut-on dire que deux polyominos sont identiques ou différents ? En fait, répondre à cette question suppose que l’on connaît les transformations que l’on a le droit d’appliquer à un polyomino donné.

Chaque polyomino peut être perçu comme un morceau d’une grille dont on aurait éventuellement déterminé un point particulier (son origine). Dans le cadre le plus général, on autorise tout mouvement de sorte que chaque petit carré constituant le polyomino soit déplacé sur un petit carré de cette grille (ou ne bouge pas !). Illustrons les possibilités par l’exemple suivant : on a représenté sur une grille un premier polyomino en bleu. Pour qu’il occupe l’emplacement rouge, il suffit de soulever le polyomino bleu et de le déplacer sans changer son orientation (on lui applique une translation) ; pour l’emplacement vert, cela ne suffirait pas, il faudrait également le faire tourner (on lui applique une rotation) ; pour qu’il occupe l’emplacement jaune, il faut obligatoirement le retourner (on lui applique une symétrie axiale).

Les mouvements qui sont autorisés peuvent ainsi être décrits comme une combinaison de plusieurs mouvements élémentaires ; de façon formelle, on dit que l’on fait agir le groupe des isométries du réseau ℤ² sur l’ensemble des polyominos.

Un polyomino étant donné, on appelle configuration tout polyomino obtenu en lui appliquant un ensemble de mouvements autorisés. Par abus, on dit généralement que deux polyominos sont identiques lorsqu’ils ont les mêmes configurations.

On peut choisir une règle plus restrictive en interdisant de retourner un polyomino ; on parle alors de déplacements (ou isométries positives). Cette alternative est moins usuelle et ne sera pas utilisée par la suite.

Hiérarchie de Golomb (version simplifiée)

On dit qu’un polyomino est :

• rectifiable lorsqu’un ensemble de ses configurations pave un rectangle,
• auto-pavant lorsqu’un ensemble de ses configurations pave un agrandissement de lui-même,
• pavant lorsqu’un ensemble de ses configurations pave le plan (la grille) en entier.

Ces propriétés ne représentent qu’une petite partie du travail de classification que Golomb a réalisé sur les polyominos selon les types de surfaces qui peuvent être pavées : des bandes, des bandes coudées, des demi-plans, etc. De nouvelles questions font immédiatement leur apparition avec ces définitions : comment prouver qu’un polyomino donné vérifie (ou non) l’une de ces propriétés ? Quel(s) lien(s) peut-on établir entre les différents types de polyominos ?

La question de savoir si un polyomino donné vérifie ou non l’une des propriétés précédemment introduites peut s’avérer d’une difficulté redoutable ; à titre d’exemple, laissons au lecteur la tâche de constituer un rectangle avec uniquement des exemplaires du polyomino de gauche, ou de celui de droite (bien que cela soit possible, il n’est pas raisonnable de croire que l’on peut réussir en se contentant d’assembler au hasard quelques pièces, du moins pour la plupart des gens !).

Appelons voisins de type 1 des polyominos qui ont au moins un côté en contact et voisins de type 0 des polyominos qui ne sont en contact que par un nombre fini non nul de sommets. Beauquier et Nivat ont montré en 1991 que l’on pouvait savoir si un polyomino donné pave le plan par translation ; cela revient à vérifier si un codage de sa frontière est d’une certaine forme. Deux cas de figure peuvent alors se présenter : un tel polyomino est un pseudo-hexagone (il admet 6 voisins de type 1 et aucun de type 0) ou un pseudo-carré (avec quatre voisins de type 1 et quatre voisins de type 0).

Nous nous contenterons de détailler les deux implications suivantes.

Introduisons un minimum de définitions avant de poursuivre. Lorsque m et n sont deux entiers naturels, notons $R(m,n)$ le rectangle constitué de n petits carrés selon l’une des longueurs et $m$ petits carrés selon l’autre ; on établit de même la définition du carré $C(n)$ contenant $n$ petits carrés par côté.

Maintenant, passons à la preuve. Si un polyomino P pave le rectangle $R(m,n)$, alors en assemblant $m$ tels rectangles on peut obtenir un rectangle $R(m,m \times n)$. On assemble alors $n$ copies de ce rectangle pour obtenir un carré $C(m \times n)$. On reproduit finalement l’assemblage de petits carrés qui définit le polyomino $P$ avec ces carrés $C(m \times n)$ afin d’obtenir un agrandissement du polyomino initial selon un facteur $n \times m$.

Commençons par remarquer que lorsqu’un polyomino est auto-pavant, l’ensemble des facteurs d’agrandissement possibles est stable par multiplication. En effet, si l’on peut paver avec des configurations d’un polyomino $P$ un agrandissement $P(n)$ selon un facteur $n$ ainsi qu’un agrandissement $P(m)$ selon un facteur $m$, alors en utilisant les pièces $P(n)$ à la place des pièces $P$ dans l’assemblage permettant de réaliser le pavage de $P(m)$, on obtient un agrandissement de facteur $m \times n$ du polyomino $P$. Ainsi, à tout polyomino auto-pavant correspond une infinité de facteurs d’agrandissement.

On note alors que, comme on peut trouver des agrandissements aussi grands que l’on veut, on peut choisir l’un d’entre eux de sorte que le polyomino initial ne se trouve pas au bord de l’agrandissement, mais se trouve complètement entouré par d’autres configurations pour fabriquer cet agrandissement. En itérant cet argument, on peut remplir en intégralité le plan sans avoir à modifier les configurations déjà placées.

Au passage, on constate que lorsqu’un ensemble de configurations d’un polyomino pave un agrandissement selon un facteur n, alors il recouvre entièrement un carré C(n). On en déduit avec la remarque précédente qu’un polyomino auto-pavant étant donné, on peut recouvrir avec certaines de ses configurations des carrés aussi grands que l’on veut. En fait, en approfondissant cette idée, on pourrait démontrer un résultat plus fort que celui qui nous intéresse ici : tout polyomino auto-pavant peut paver un quadrant, autrement dit l’ensemble des carreaux dans un quadrillage dont les deux coordonnées sont positives (par exemple).

Comme on vient de prouver des implications, il est légitime de chercher à savoir si leurs réciproques sont vraies ou non. Il n’est pas difficile de trouver des polyominos pavant le plan qui ne sont pas auto-pavant. C’est par exemple le cas du pentamino suivant.

Une condition nécessaire que doit vérifier un polyomino rectifiable est que parmi toutes ses configurations, l’une d’entre elles soit constituée d’un petit carré qui ait à la fois la plus petite abscisse et la plus petite ordonnée parmi les coordonnées de tous les petits carrés la constituant. Cela n’est pas le cas de ce pentamino !

Remarquons que l’on ne peut constituer que deux pavages différents du plan avec ce pentamino ; ces pavages sont de type pseudo-carrés et vérifient une forte propriété de régularité, ils sont périodiques selon deux directions, ou bipériodiques. Ainsi, on peut trouver pour chacun deux vecteurs u et v de sorte que le pavage de la grille soit réalisé par toutes les configurations obtenues en appliquant au polyomino initial les translations de la forme n u + m v, où n et m prennent toutes les valeurs entières.

Noter que si un polyomino est pavant, il est possible que certains de ses pavages ne soient pas bipériodiques. Pour s’en convaincre, il suffit de constituer avec des dominos des lignes d’épaisseur 1 que l’on empile les unes sur les autres de la façon la plus désordonnée possible ; on obtient de la sorte des pavages périodiques selon une direction.
Au passage, on peut aussi se poser la question de savoir s’il existe un polyomino pavant qui ne définirait que des pavages non périodiques. Le problème avec cette question est qu’elle nous entraîne dans le monde compliqué de l’indécidabilité, où (pour faire simple) on peut énoncer des propriétés dont on ne saura jamais si elles sont satisfaites ou non.

On vient donc de résoudre le cas de la deuxième réciproque ; à ce jour, la première est toujours une question ouverte :

Existe-t-il un polyomino auto-pavant qui n’est pas rectifiable ?

Colorabilité

Revenons à une question que l’on a laissée temporairement de côté : étant donnés deux polyominos P1 et P2, de quels critères dispose-t-on afin de déterminer s’il est possible ou non de paver le polyomino P2 avec le polyomino P1 ?
Il existe plusieurs cas particuliers bien connus de cette question. Peut-être celui qui est le plus souvent présenté est le suivant : déterminer s’il est possible de paver avec des dominos le carré C(8) auquel on a enlevé deux coins opposés.

Un premier critère évident est une condition nécessaire à la réalisation d’un pavage : il faut que le nombre de petits carrés qui constitue le polyomino à paver soit un multiple du nombre de petits carrés qui constitue le polyomino paveur ; le quotient entre ces deux quantités représentant le nombre de configurations à placer. Toutefois, cette condition ne suffit pas, car il n’est pas possible de placer 31 dominos dans notre carré mutilé. Afin de prouver cela, on utilise un argument de colorabilité. Si notre surface était coloriée comme un échiquier, on noterait qu’elle est constituée de 32 carrés blancs et 30 carrés noirs (ou l’inverse). Mais chaque fois que l’on pose un domino sur cette surface, ce domino recouvre une case blanche et une case noire. Aussi, on pourra placer au maximum 30 dominos sur cette surface et il restera 2 carrés non recouverts de la même couleur.

Cette idée peut être formalisée afin de fournir dans un grand nombre de cas une impossibilité de réaliser un pavage. Pour savoir si un ensemble de configurations du polyomino P1 pave un polyomino P2, on essaie d’associer à chaque case du polyomino P2 une certaine valeur, de sorte que quel que soit l’endroit où l’on pose une configuration du polyomino P1, la somme des valeurs des cases concernées par cette configuration soit constante. Pour revenir à l’exemple précédent, si l’on dit qu’une case blanche vaut 1 et qu’une case noire vaut -1, alors tout domino vaut 0, or le carré mutilé vaut 2 (ou -2), donc on ne peut pas le paver avec des dominos. Pourrez-vous prouver qu’il est impossible de paver le carré $C(10)$ avec des tétraminos en forme de $T$ ? (Plusieurs méthodes légèrement différentes permettent d’arriver à ce résultat)

Malheureusement (ou heureusement ?), encore une fois cette jolie idée ne fournit qu’un critère. Autrement dit on peut très bien ne pas identifier d’impossibilité apparente et l’on ne peut alors rien en conclure. Par exemple, on vérifie aisément qu’en coloriant l’hexamino suivant, on obtiendrait autant de cases blanches que de cases noires, pourtant on ne peut pas le paver avec des dominos.

Un autre inconvénient est que cette méthode ne peut pas être utilisée pour n’importe quel polyomino. Par exemple, on n’obtient rien d’intéressant avec le triomino coudé.
Essayons de comprendre pourquoi ; on considère pour cela une surface contenant un carré $C(2)$. Supposons que l’on ait pu attribuer à chaque case une certaine valeur : l’une vaut $a$, une autre vaut $b$, une troisième vaut $c$ et la dernière vaut $d$. En posant à n’importe quel endroit notre triomino, les sommes possibles sont $a+b+c, a+b+d, a+c+d $ et $b+c+d$ ; si l’on veut que ces sommes soient toutes égales, alors on aboutit à la relation $a=b=c=d$. Ainsi, il n’est pas possible de distinguer les cases en leur attribuant des valeurs différentes.

Cette objection a été approfondie par Conway et Lagarias, qui ont montré qu’il était parfois obligatoire de définir des objets mathématiques nettement plus sophistiqués pour tenter de résoudre notre problématique !

Conclusion et ouvertures

On a abordé plusieurs questions délicates auxquelles les mathématiciens ne savent pas répondre à ce jour. Aussi, confronté à des problèmes compliqués, le premier réflexe est de chercher des questions encore plus difficiles ! Passons en revue différentes possibilités pour un mal au crâne assuré (cette liste étant de très loin non exhaustive) :

• Il existe de nombreux problèmes avec d’autres formes que des polyominos.
  Parfois, les formes restent encore simples avec par exemple des assemblages de triangles équilatéraux (polydiamants, sphinx, etc.), mais on peut également généraliser le cadre introduit ici à des formes beaucoup plus irrégulières !
• On peut aussi changer la nature des pièces en augmentant la dimension de l’espace de travail. Aussi, qu’en est-il de nos questions si l’on remplace nos petits carrés par des petits cubes ou par des petits hyper-cubes en dimension 4, 5, 37, n ?
• On a vu que pour un polyomino auto-pavant, l’ensemble S des facteurs d’agrandissement est un sous-ensemble des entiers naturels qui est stable par multiplication. Réciproquement, si l’on se donne un ensemble S vérifiant cette propriété, peut-on trouver un polyomino auto-pavant dont les facteurs d’agrandissements sont les éléments de cet ensemble ? De façon concrète, si cet ensemble S est : l’ensemble des nombres impairs ? L’ensemble des nombres qui sont constitués d’au moins deux facteurs premiers ? Tous les cubes d’entiers ? Tous les entiers sauf 2 ?
  Ici aussi, on peut bien entendu étendre le problème en dimension supérieure.
• Nous n’avons pas évoqué l’ordre d’un polyomino, défini par Klarner comme le plus petit nombre de configurations permettant de paver un rectangle, grâce auquel on peut former de nouvelles questions.
• Dans tout ce qui précède, nous n’avons considéré que des pavages constitués d’un seul type de polyomino.
  On peut aussi s’intéresser aux pavages constitués de polyominos différents, ce qui permet de poser de nouveaux problèmes de décidabilité.
  Le lecteur averti n’hésitera pas à consulter les récents travaux de Nicolas Ollinger pour en savoir davantage !

Enfin, pour ne pas laisser le lecteur complètement frustré devant autant de questions non résolues, un exercice nettement plus accessible que les problématiques précédemment soulevées : montrer que pour le triomino coudé, tout entier naturel est un facteur d’agrandissement.

Pour en savoir plus

Les lecteurs restés sur leur faim trouveront de quoi nourrir leur appétit avec ces ressources :

• J. B. Kelly : Polynomials and Polyominoes. American Mathematical Monthly 76 (1966), 464-471. Où l’on voit comment définir des polynomes afin de généraliser les arguments de colorabilité.
• J. Propp : A pedestrian approach to a method of Conway, or, A Tale of Two Cities. Mathematics Magazine, Vol. 70, No 5 (Dec 1997), pp. 327-340. Cet article se concentre sur le pavage de diamants Aztèques avec un tétromino particulier.
• J. H. Conway & J. C. Lagarias : Tiling with polyominoes and combinatorial group theory, Journal of Combinatorial theory, Series A, No 53, 1990, pp. 183-208 ainsi que Thurston : Conway’s tiling groups, The American Mathematical Monthly, Vol. 97, No 8, Special geometry issue (Oct. 1990), pp. 757-773. Dans ces articles, on trouve les notions de coloration généralisée et d’invariance de frontière, avec comme jolie application l’étude de tribones.
• la plupart des livres de Martin Gardner !
• les livres Polyominoes : Puzzles, Patterns, Problems, and Packings de Solomon W. Golomb et Polyominoes : A Guide to Puzzles and Problems in Tiling de George E. Martin.

On peut également trouver sur internet beaucoup de ressources sur notre sujet. Il est plutôt ingrat de devoir faire un tri parmi toutes celles qui existent car de nombreux auteurs ont de très belles pages fournies qui méritent amplement d’être consultées. Un avis personnel (avec mes excuses pour les autres !) est que le site de Michael Reid devrait être exploré en priorité, avec comme bonus quelques solutions à certains problèmes exposés au cours de la lecture.