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.

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.

É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) :

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é !