Dominos apériodiques

Un record définitif établi en 2015 par une preuve mi-informatique, mi-mathématique

Piste bleue Le 6 mars 2018  - Ecrit par  Thomas Fernique Voir les commentaires (2)

Étant donnés quelques carrés aux bords colorés, appelés dominos, qu’on place côte à côte de sorte que les bords se touchant soient de la même couleur, on veut savoir si l’on peut recouvrir tout le plan avec des copies de ceux-ci. La question s’avère très difficile à cause de l’existence de dominos apériodiques. On survole ici l’histoire de ces dominos apériodiques, des premiers découverts en 1964 jusqu’aux derniers trouvés par Emmanuel Jeandel et Michaël Rao en 2015.

Le problème des dominos

On se donne quelques carrés dont les bords sont colorés qu’on pose sur la table en suivant la règle des dominos [1] : deux carrés ne peuvent se toucher que le long de bords de la même couleur. Pour cette raison, et bien que les dominos usuels soient rectangulaires, on appellera dans toute la suite ces carrés colorés des dominos. Il y a encore deux règles spécifiques :

  • Le jeu de dominos comporte un nombre fini de dominos différents, mais chaque sorte peut être utilisée autant de fois que l’on veut.
  • Un domino ne peut être ni tourné ni retourné, mais seulement déplacé.

Ci-dessous, un petit exemple avec un jeu de quatre dominos.

PNG - 10.3 ko

Le problème des dominos, introduit par Hao Wang au début des années 60 pour modéliser un problème de logique, est de décider si oui ou non il est possible de recouvrir ainsi le plan tout entier (on parle de pavage du plan et les dominos sont appelés tuiles de Wang).

Non

Une première approche consiste à simplement essayer de former avec ces dominos des carrés de plus en plus grands. Le plan étant infini, ça peut être très long (surtout vers la fin). Mais si jamais il existe une taille de grand carré qu’il est impossible d’obtenir, alors a fortiori il est impossible de recouvrir tout le plan et on peut répondre « non ». C’est le cas des quatre dominos ci-dessous : jamais vous n’arriverez à former un carré 4x4 [2].

Réciproquement, on montre que si n’importe quelle taille de grand carré peut être obtenue, alors on peut recouvrir le plan tout entier, de sorte qu’on a un moyen de détecter quand un jeu de dominos ne peut pas recouvrir le plan.

Démonstration de ce sens réciproque.

Il s’agit d’un argument diagonal un peu délicat mais classique.

Supposons que, pour tout $n\geq 0$, on puisse former avec ces dominos un carré $C_n$ de taille $n\times n$.

Soit $k\geq 0$. Parmi l’infinité de carrés $(C_n)_{n\geq k}$, un nombre infini sont des extensions du même carré $k\times k$ (une extension est obtenue en ajoutant des dominos sans modifier ceux déjà placés). En effet, il y a un nombre fini de tels carrés $k\times k$ possibles. Or si on range un nombre infini de chaussettes (les $C_n$) dans un nombre fini de tiroirs (les carrés $k\times k$), alors au moins un des tiroirs contient une infinité de chaussettes. Soit donc $D_k$ un tel carré $k\times k$. On supprime alors tous les $C_n$ qui n’en sont pas une extension et on recommence le même processus avec la famille $C_n$ modifiée, qui est toujours infinie, et une valeur de $k$ plus grande.

On obtient ainsi une famille $(D_k)$ de carrés de plus en plus grands, tels que chaque carré est une extension des carrés plus petits. On peut alors passer à la limite pour obtenir un recouvrement du plan entier : en une position donnée, on place le domino qui est à cette position dans les $D_k$ suffisamment grands pour atteindre cette position (et tous ces $D_k$ donnent bien le même domino).

Évidemment ce moyen est un peu fastidieux, mais il existe un outil très pratique pour ce genre de travail : l’ordinateur. N’idéalisons cependant pas cet outil : le nombre de possibilités à tester devient vite énorme quand la taille de ce carré augmente [3], et l’ordinateur, malgré sa puissance de calcul, pourrait bien manquer de mémoire ou ne pas répondre avant de nombreuses années... Par exemple, Emmanuel Jeandel et Michaël Rao ont vérifié par ordinateur que le jeu de dominos ci-dessous pouvait former des carrés de taille jusqu’à 200x200, mais ont ensuite abandonné devant le temps nécessaire à vérifier plus loin [4].

Mentionnons d’ailleurs que personne n’a pu résoudre le puzzle Eternity 2, qui consiste à former un carré de 16x16 dominos, malgré un prix de 2 millions de dollars à la clef...

Néanmoins, d’un point de vue théorique, nous avons bien un algorithme qui finira par répondre « non » si jamais il est impossible de recouvrir tout le plan.

Oui

Il se peut aussi, lorsqu’on essaie de former des carrés de plus en plus grands, qu’on tombe sur un grand carré dont les bords gauche et droit sont les mêmes. On peut alors répéter horizontalement ce carré pour former une ligne infinie. Si en plus les bords inférieur et supérieur de ce grand carré sont aussi identiques, alors on peut aussi répéter verticalement ce carré et recouvrir le plan tout entier. On parle de recouvrement périodique. Par exemple, le jeu de quatre dominos ci-dessous permet de former un carré 2x2 qu’on peut répéter horizontalement et verticalement.

Un aperçu du recouvrement périodique du plan qu’on peut alors obtenir (le carré 2x2 qui se répète périodiquement est encadré) :

Bien entendu le problème du grand nombre de possibilités à essayer demeure, et même un ordinateur mettra par exemple beaucoup de temps avant de trouver que le jeu de dominos ci-dessous permet de former un carré 30x30 qui peut être répété périodiquement.

Néanmoins, encore une fois d’un point de vue théorique, nous avons un algorithme qui finira par répondre « oui » si jamais il existe un recouvrement périodique.

Apériodicité

On sait maintenant détecter quand un jeu de dominos ne peut pas recouvrir le plan ou peut le faire périodiquement. Mais se pourrait-il qu’on tombe sur un jeu qui permette de former des carrés toujours plus grands sans que jamais on ne tombe ni sur un carré impossible à recouvrir, ni sur un carré qui peut être répété périodiquement ?
Hao Wang pensait que non, mais son étudiant Robert Berger montra l’inverse en 1964, construisant explicitement un ensemble de dominos qui pouvait recouvrir le plan mais seulement de façon non périodique. On parle de dominos apériodiques. Soulignons qu’il est facile de trouver des dominos qui pavent non-périodiquement ou périodiquement : toute la difficulté est de ne paver que non-périodiquement.

Dans la foulée, Berger utilisa ces dominos [5] pour montrer qu’il n’existait pas d’algorithme permettant de décider, en toute généralité, si un jeu de dominos permettait de recouvrir le plan ou pas : il s’agit d’un problème indécidable. Ce qui n’exclut cependant pas de résoudre des cas particuliers (ce qu’on a déjà fait ci-dessus).

Le jeu construit par Berger est un peu compliqué, mais un jeu plus simple fut découvert en 1971 par Raphael Robinson [6], le plus souvent représenté par 6 pièces de puzzle qui peuvent, elles, être tournées et retournées (chaque position différente d’une même pièce correspondant à un domino dont les couleurs dépendent des indentations de la pièce, une étude de cas montrant qu’il y a alors 56 dominos différents) :

Robinson montre que ces pièces permettent de recouvrir le plan entier, et que la seule façon de procéder est de former, si l’on regarde les lignes dessinées sur les pièces, une hiérarchie infinie de carrés de plus en plus grands, ce qui interdit la périodicité car il faudrait que le carré répété soit arbitrairement grand (cliquez pour agrandir) :

PNG - 932.8 ko

Des tuiles qui calculent

D’autres jeux de dominos apériodiques furent trouvés dans les années 70, basés sur la même idée de structure hiérarchique. Jusqu’en 1996, où Jarkko Kari construit un jeu de seulement 14 dominos apériodiques (le record précédent était de 16) fonctionnant sur un tout autre principe [7] :

Pour comprendre l’idée de Kari, il faut voir les couleurs comme des nombres. Chaque domino s’avère alors effectuer un petit calcul, le recouvrement du plan correspondant à un grand calcul. Plus précisément, associons comme ci-dessous un nombre à chaque côté des quatre dominos de la première ligne :

Ces nombres sont tels que, pour chaque domino, la somme du double du nombre sur son côté Nord et du nombre sur son côté Ouest est égale à la somme des nombres sur ses côtés Sud et Est [8] :

\[ 2N+O=S+E. \]

Pour le premier des quatre dominos ci-dessus, par exemple, on a

\[ 2\times 1+(-1)=2+(-1). \]

En d’autres termes, chaque domino effectue une multiplication par deux, avec une retenue entrant par le côté Ouest et une sortant par le côté Est.

Ces dominos peuvent ensuite être combinés en ligne pour multiplier des nombres plus grands. Ainsi, l’exemple ci-dessous montre le calcul $2\times 5-1=10-1$ effectué par une combinaison de sept dominos telle que

  • la somme des nombres sur les côtés Nord vaut $5$
  • la somme des nombres sur les côtés Sud vaut $10$
  • la retenue entrante sur le côté Ouest vaut $-1$
  • la retenue sortante sur le côté Est vaut $-1$

Les 10 dominos des deux dernières lignes fonctionnent de la même manière mais effectuent, eux, une division par trois. Remarquons qu’une même ligne ne peut pas mélanger des dominos de la première ligne et des deux suivantes car les couleurs utilisées sur les bords gauche et droit sont disjointes.

L’impossibilité de recouvrir périodiquement le plan vient alors du fait qu’étant donné un nombre non nul, quelle que soit la façon dont on enchaîne une suite de multiplications par 2 ou divisions par 3, on ne retombera jamais sur le même nombre ! Plus précisément, supposons qu’il existe un grand carré qui peut être répété périodiquement et notons respectivement $p$ et $q$ les nombres de lignes formées de dominos multipliant par deux ou divisant par trois, alors la somme $h$ des nombres sur chacun des côtés horizontaux de ce grand carré répétable vérifie l’équation [9] :

\[ 2^ph=3^qh, \]

ce qui est impossible [10]. Il ne peut donc pas y avoir de recouvrement périodique ! Jarkko Kari montre aussi qu’on peut effectivement recouvrir le plan [11].

Onze dominos, pas un de moins

Kari a peu après gagné un carré en changeant les coefficients des multiplications effectuées, abaissant le record du plus petit jeu de dominos apériodiques à 13 dominos. Pouvait-on faire mieux ? C’est le défi auquel se sont attelés Emmanuel Jeandel et Michaël Rao entre 2010 et 2015 [12].

L’idée générale est simple : pour chaque jeu de dominos possible (en commençant par les plus petits), on essaie de former des grands carrés de plus en plus grands. De trois choses l’une :

  1. on trouve une taille de carré qui n’est pas faisable : les dominos ne pavent pas.
  2. on trouve un grand carré qui peut être répété : les dominos pavent périodiquement.
  3. le temps se fait long ou l’ordinateur n’a plus assez de mémoire : on a un ensemble de dominos candidat à l’apériodicité.

C’est la dernière éventualité qui nous intéresse : il faut alors examiner le jeu à la main et réfléchir ! Il se peut qu’on retombe alors dans une des deux premières éventualités. Pour limiter ces échecs, il faut optimiser la façon dont cherche l’ordinateur, et c’est une des prouesses du travail d’Emmanuel Jeandel et Michaël Rao.

Leur programme a permis de montrer en quelques mois de calcul que tous les ensembles de 10 dominos ou moins tombaient dans les deux premiers cas, sauf un pour lequel ils ont démontré à la main qu’il ne recouvrait pas le plan. Pour les ensembles de 11 dominos, tous tombaient encore dans les deux premiers cas, sauf 26 qui résistaient. En particulier celui-ci :

Emmanuel Jeandel et Michaël Rao ont pu démontrer à la main que le jeu ci-dessus était effectivement apériodique. C’est donc un nouveau record, définitif celui-ci puisque tous les jeux plus petits pavent périodiquement ou ne pavent pas ! Au pire il devra peut-être partager la première marche du podium avec quelques-uns des 25 autres candidats restants, par exemple celui-ci :

Ce résultat combine donc une preuve informatique via une recherche exhaustive par ordinateur et une preuve mathématique du fait qu’un des ensembles candidats est effectivement apériodique. Une seule pointe de regret : le tenant du titre recouvre le plan de façon hiérarchique [13], comme les premiers exemples trouvés. Se pourrait-il que parmi les 25 candidats restants il en existe un qui soit apériodique mais ne recouvre le plan ni hiérarchiquement ni comme le précédent record de Kari ? Il s’agirait alors d’un nouveau type d’apériodicité !

Post-scriptum :

L’auteur et la rédaction de Images des Maths remercient les relecteurs Quentin, Rémi Molinier, Claire Wenandy et Agirand pour leur relecture attentive et leurs commentaires constructifs.

Ce sujet semble à la mode puisqu’un autre article sur le sujet a récemment été publié (la rédaction de celui-ci étant déjà pratiquement achevée). Le lecteur intéressé trouvera certainement profit à le lire également !

Article édité par Jérôme Buzzi

Notes

[1Ou le jeu Tetravex pour ceux qui connaissent.

[2On peut essayer toutes les possibilités mais aussi préférer un argument théorique : si trois dominos sont empilés verticalement, la couleur du bas est nécessairement vert, celle du haut rouge, et aucun domino ne peut être mis ni au-dessus ni en dessous.

[3Plus précisément, le nombre de possibilités croît exponentiellement en le nombre de dominos

[4Malins, ils ont préféré trouver un argument théorique montrant qu’il existait une taille de carré qui ne pouvait pas être atteinte.

[5combinés à d’autres dominos simulant le calcul d’une machine de Turing

[6Raphael Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae 12 (1971), pp. 177–209.

[7Jarkko Kari, A small aperiodic set of Wang tiles, Discrete Mathematics 160 (1996), pp. 259–264.

[8L’habitude est de parler de côtés Nord, Ouest, Sud et Est pour, respectivement, haut, gauche, bas et droit.

[9Les côtés est et ouest d’un grand carré répétable étant égaux, ils n’interviennent pas dans cette équation.

[10On a $h\neq 0$ car les dominos de la première ligne ne permettent pas en effet de faire une ligne avec que des $0$ au nord, quant à ceux des deux lignes suivantes, dont l’interprétation des couleurs en termes de nombres n’a pas été donnée ici, ils n’ont aucun $0$ sur les côtés nord ou sud.

[11L’idée est que la moyenne des chiffres sur les côtés nord d’une ligne code un nombre réel entre $1/2$ et $3$, et il faut alors montrer que si ces chiffres sont « harmonieusement répartis », les multiplications par deux ou divisions par trois peuvent être effectuées indéfiniment. Sans être extrêmement difficile, cette démonstration déborde cependant le cadre de cet article.

[12Emmanuel Jeandel et Michaël Rao, An aperiodic set of 11 Wang tiles, prepublication disponible sur arXiv.

[13Un recouvrement est hiérarchique si ses dominos peuvent être groupés en « super-dominos » de sorte à obtenir un recouvrement qui, à recodage des super-dominos en dominos près, est identique au recouvrement original.

Partager cet article

Pour citer cet article :

Thomas Fernique — «Dominos apériodiques» — Images des Mathématiques, CNRS, 2018

Commentaire sur l'article

  • Dominos apériodiques

    le 18 mai à 11:24, par Niak

    Merci pour cet article. Le « candidat » proposé à la fin semble incorrect, les dominos 1 et 9, ou encore 7 et 9, s’assemblent verticalement pour former des rectangles 2x1 qui pavent périodiquement. En supposant qu’il n’y a qu’une seule erreur de couleur sur le domino 9, remplacer sa couleur Est par du jaune semble fournir un « candidat » plus robuste (mais je ne sais pas si c’est la bonne correction).

    Répondre à ce message
    • Dominos apériodiques

      le 18 mai à 12:29, par Thomas Fernique

      Après vérifiation c’est exactement ça : ça doit être du jaune sur le côté est du domino 9. Bravo !
      Je vais voir comment changer le dessin.

      Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM