O que significa "Problema do Dominó"?
Índice
O problema do dominó é uma questão na teoria de azulejos que pergunta se é possível cobrir uma superfície plana inteira usando um conjunto dado de azulejos, seguindo regras específicas.
Azulejos Wang
Um tipo comum de azulejo usado nesse problema é o azulejo Wang. Esses são azulejos quadrados que têm cores nas bordas. Os azulejos podem ser colocados um ao lado do outro apenas se as cores nas bordas que se tocam combinarem.
Decidibilidade
Em geral, é sabido que o problema do dominó é indecidível, ou seja, não há um único método que funcione para todas as situações possíveis. No entanto, para um grupo especial de azulejos conhecido como conjuntos de azulejos robustos, o problema pode ser resolvido. Conjuntos de azulejos robustos ou não conseguem cobrir o plano de jeito nenhum ou conseguem sob condições específicas.
Azulejos Não-Periódicos
Tem um novo tipo de azulejo com azulejos quadrados que não se repete em um padrão regular. Esse método usa regras locais simples, tornando fácil entender por que esses azulejos não formam um padrão repetitivo.
Grupos Hiperbólicos
Em um contexto diferente, para certos grupos conhecidos como grupos hiperbólicos, foi mostrado que não há método para determinar se uma coleção de dominós pode cobrir uma estrutura complexa chamada grafo de Cayley, especialmente quando as cores precisam combinar nos pontos onde as bordas se encontram. Isso destaca a complexidade e o desafio de resolver o problema do dominó em várias situações.