8 votos

¿Son todos los poliominos con lados uniformes enlosables por los dominós?

En este trabajo (Sección 8) el autor afirma que es "trivial" para demostrar que un polyomino con todas las partes (incluyendo los lados de los agujeros en la polyomino) incluso tiene un suelo de baldosas por las fichas de dominó.

enter image description here

De hecho, es fácil ver por polyominoes sin agujeros, pero el caso general, no parece tan obvio para mí. Una cosa que hace que sea difícil es que los agujeros pueden aparecer en cualquier lugar siempre que sus fronteras no se superponen o coinciden. (Esto hace que sea difícil encontrar una prueba de que reduce la cifra pero mantiene incluso-lados restricción.)

Hay, de hecho, un trivial prueba de esto?

Nota: le pregunté a una pregunta anterior acerca de lo que el mismo autor llama "incluso" polyominoes, pero los polyominoes son completamente diferentes.

7voto

Kenneth Posey Puntos 123

Después de pensar en ello todo el día descubrí un trivial de la prueba.

Primera nota de que cualquier figura con todos los lados, incluso y sin agujeros pueden ser revestidas con fichas de dominó, de modo que todos ellos son horizontales, y que cada una de las acciones de domino su borde largo con en la mayoría de los uno de los otros domino.

Ahora tomar cualquier figura con todos los lados incluso, posiblemente con agujeros (cuyos lados también deben ser todas iguales). Primera baldosa es como si no tuviera agujeros. A continuación, quitar todas las fichas de dominó que se encuentran completamente dentro de un agujero. Algunas fichas de dominó puede cruzar la frontera del agujero. Estas fichas de dominó debe ocurrir en pares (desde el agujero lados tienen longitud), de manera que cada par que se superpone a un agujero de la frontera puede ser reemplazado con un domino fuera del agujero. El mosaico es completa.

A continuación se describe el procedimiento en la figura anterior.

La prueba también funciona si el borde exterior sólo tiene todos los lados horizontales de longitud y todos los agujeros tienen sus lados verticales incluso de longitud.

Actualización: La prueba también funciona para las figuras con lados divisible por $n$ y bares de la longitud de la $n$ en lugar de fichas de dominó si los agujeros son, al menos, $n - 1$ unidades de distancia. Creo (pero no estoy seguro) que nos puede quitar esta restricción si el azulejo conjunto es todo lo $n$-ominoes.

enter image description here

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X