problème des dominos de Wang

problème du domino
pavage de Wang
tuile de Wang

GEOMETRIE

Hao Wang a proposé en 1961 un ensemble de tuiles (ou dominos) qu’on peut représenter comme un ensemble de carrés, colorés sur chacun de leurs côtés, autrement dit un ensemble de quadruplets. On les agence de telle façon que les couleurs des côtés correspondants soient les mêmes.
Wang a conjecturé que si un ensemble fini de telles tuiles pavait le plan, alors il existerait un pavage périodique du plan. C’est le problème des dominos de Wang.
En 1966, Robert Berger, un élève de Wang, a résolu cette conjecture par la négative. Une conséquence est qu’il n’existe pas d’algorithme permettant de décider si un ensemble donné de tuiles pave ou non périodiquement le plan. Berger a trouvé un ensemble de 20 426 tuiles permettant un pavage apériodique du plan. C’était là le premier exemple de pavage apériodique.
Il existe des généralisations des tuiles de Wang, comme la généralisation à l’espace à trois dimensions.