Que signifie "Problème de dominos"?
Table des matières
Le problème du domino, c'est une question dans la théorie du carrelage qui demande s'il est possible de recouvrir toute une surface plate avec un ensemble de tuiles donné tout en respectant des règles spécifiques.
Tuiles Wang
Un type courant de tuile utilisé dans ce problème, c'est la tuile Wang. Ce sont des tuiles carrées qui ont des couleurs sur leurs bords. Les tuiles peuvent être placées côte à côte seulement si les couleurs des bords qui se touchent correspondent.
Décidabilité
En général, on sait que le problème du domino est indécidable, ce qui veut dire qu'il n'y a pas de méthode unique qui marche pour chaque situation possible. Cependant, pour un groupe spécial de tuiles connu sous le nom de tuiles robustes, le problème peut être résolu. Les tuiles robustes ne peuvent soit pas recouvrir le plan du tout, soit le faire sous certaines conditions spécifiques.
Carrelages Non-Périodiques
Il y a un nouveau type de carrelage avec des tuiles carrées qui ne se répète pas de manière régulière. Cette méthode utilise des règles locales simples, ce qui rend facile de comprendre pourquoi ces tuiles ne forment pas un motif répétitif.
Groupes Hyperboliques
Dans un contexte différent, pour certains groupes appelés groupes hyperboliques, il a été montré qu'il n'y a pas de méthode pour déterminer si une collection de dominos peut recouvrir une structure complexe appelée un graphe de Cayley, surtout quand les couleurs doivent se correspondre aux points où les bords se rencontrent. Ça met en avant la complexité et le défi de résoudre le problème du domino dans divers scénarios.