¿Es cada poliominó "uniforme" con un agujero Enlosables por fichas de dominó?

Question

En Invariancia conforme de Domino de ordenamiento en teselas el autor define una incluso polyomino como un polyomino con todas las esquinas (de todas las fronteras, de dentro y de fuera), "negro", si el polyomino es de color con el tablero de ajedrez para colorear. Una esquina es negro, si el ángulo interior se encuentra en un cuadrado negro, como este:

Aquí están algunos ejemplos:

Mi pregunta es si es cierto que aún polyomino con un agujero es siempre enlosables por fichas de dominó.

---

Antecedentes: Una relacionada con el polyomino se llama Temperleyan polyomino (en el mismo papel), que se forma a partir de una aún polyomino mediante la eliminación de uno negro de la esquina desde el borde exterior, y añadiendo un negro de células para cada interior de la frontera. Aquí están algunos ejemplos:

El documento muestra (aunque no realmente en una forma en la que puedo seguir) Temperleyan polyomino son enlosables por fichas de dominó.

También es fácil mostrar que la deficiencia (negro menos glóbulos blancos) en un polyomino con $H$ agujeros es $1 - H$, por lo que aún polyomino con 1 agujero es equilibrada (tiene el mismo número de blanco y negro de las células).

Los agujeros de incluso polyominoes son incluso.

Answer 1

Esto es cierto! Aún polyomino con un agujero es en mosaico por fichas de dominó.

La prueba tiene abajo un par de vagos elementos; una prueba sin ellos, será bueno.

Prueba. Para esta prueba a trabajar, vamos a manipular la frontera (ya sea en el exterior o en el interior de la frontera) para dar un nuevo polyomino con un agujero, y vamos a considerar las regiones donde las fronteras se superponen también válido polyominoes, y son, incluso si las esquinas son de color negro con la definición simple. Aquí están algunos ejemplos de tales polyominoes (el borde exterior ha sido ligeramente desplazadas, donde coincide con el interior de la frontera).

Aquí, en mosaico significa enlosables por fichas de dominó.

1. Un anillo es un polyomino donde cada celda tiene exactamente dos fronteras. Todos los anillos son de mosaico.

2. Un pico es una célula con exactamente un vecino. En un polyomino, todos los picos deben ser de color negro (de lo contrario no son blanco de las esquinas). También, todos los picos de negro debe estar conectado a una celda blanca con exactamente dos vecinos. Para ello, en un polyomino, si nos movemos de la frontera para excluir el pico y la vecina de la célula, todavía estamos a la izquierda con un polyomino.

Un ejemplo de esta manipulación:

3. Un $2 \times 2$ plaza puede ser de dos tipos. El tipo I tiene un cuadrado negro en la parte superior derecha, una de Tipo II, la plaza tiene un cuadrado negro en la parte superior izquierda. Si un Tipo que la plaza se produce en una esquina de la polyomino, podemos mover la frontera para excluirlo, y mantener la polyomino incluso.

Un ejemplo de esta manipulación:

4. Todos convexa de las esquinas de un polyomino son uno de estos cuatro tipos:

(Esta parte es un poco vagos; requiere considerar muchos casos).

5. Si llevamos a cabo las manipulaciones en 2 y 3 hasta que no podemos, estamos sólo a la izquierda con los siguientes tipos de esquinas convexas:

6. Una figura con sólo tipo 3 y 4 esquinas convexas y un agujero no puede contener un $2\times2$ subfigure.

Supongamos que hay una plaza. Encontrar la más grande conectado conjunto de celdas que contiene esta plaza, de tal manera que cada célula es parte de una $2\times 2$ subfigure. Este conjunto de células que debe tener al menos cuatro esquinas convexas (como lo hacen todas las figuras rectilíneas). Por estas esquinas para no ser de las esquinas de la figura entera, cada uno debe ser "cubiertos" por una "hebra" (la imagen de abajo muestra una posibilidad.) Estas líneas deben resultar en picos, o que se debe conectar en pares. Si se conectan en pares, hay dos agujeros, y esto es imposible. Por ello, no puede existir $2\times 2$ subfigure.

En este^ de la imagen, hay un $2 \times 2$ plaza, contenida en un $3\times 3$ plaza donde cada rincón está cubierto por una blanca de la célula que las estrellas de la cadena. En este ejemplo, las hebras conectar en parejas, dando lugar a dos agujeros.

7. No podemos tener X o T uniones en una figura con el no $2\times2$ subfigures, sin picos, y un agujero.

Supongamos que tenemos una X junction. Cada uno de los cuatro conectores deben llevar finalmente a un pico, o pares de ellos debe unirse. En el último caso, tenemos dos agujeros, lo cual es imposible. Para ello no hay ningún X uniones.

Supongamos que tenemos un cruce. Cada uno de los tres conectores debe conducir a un pico, o ellos deben unirse a otros conectores. Sólo podemos unir si tenemos, al menos, otro cruce en T, en cuyo caso tendremos al menos tienen dos orificios, lo cual es imposible. Para ello no hay T uniones.

8. Esto significa que ya sea un anillo, o un polyomino con ningún área (de ahí el interior y exterior de la frontera coinciden totalmente).

(Esto también es incompleto, y requieren de casos para asegurarse de que no podemos tener otras posibilidades.)

7. Este procedimiento muestra que podemos partición cualquiera incluso polyomino con un agujero en un conjunto con $dominoes$, $2\times2$ plazas, y ya sea un anillo o vacío polyomino. Todos los elementos de la partición están en mosaico, y para ello, lo es toda la figura.

---

Algunas observaciones:

• El borde doble definición es necesaria para lidiar con la polyominoes como este de abajo. Si no tuviéramos que, la eliminación de una $2\times 2$ esquina no dejaría aún polyomino. (Sería bueno encontrar una prueba que no requiere de este truco.)

• Un algoritmo que se sigue inmediatamente de la frontera manipulaciones.

Answer 2

Esta respuesta es un esquema. Sin embargo, creo que abarca todos los casos.

Llamar a un polyomino con el mismo número de blanco y negro de las células y no hay agujero tipo 1. Llame incluso polyomino con un solo agujero tipo 2.

En primer lugar observamos que un tipo 1 polyomino puede ser en forma de mosaico. Esto es porque está vacía o no hay un rincón en el que podemos colocar una ficha de dominó tal que el resto de las células son de tipo 1.

Ahora vamos a comprobar que el tipo 2 de polyomino puede ser distribuidas por inducción de su tamaño. Considere el grafo cuyos vértices son las células y en el agujero de la polyomino y cuyos bordes ir entre las células de intercambio de un lado.

• Si el gráfico tiene un corte vértice, entonces tiene un corte blanco vértice $v$. Cortar el polyomino en cualquier lado de la $v$ hojas de $v$ en el lado opuesto del agujero. El resultado es un tipo 1 polyomino en el lado con $v$, ya que tiene uno blanco de la esquina y no hay agujero, y uno menor de tipo 2 polyomino en el otro lado.
• Si la gráfica no tiene corte de vértices, a continuación, el conjunto de vértices con al menos una de las esquinas de tocar el exterior (sin límites de la región) se compone de un número finito de longitud de segmentos rectos, cada uno va de una esquina (inclusive) a otro (exclusivo), ninguno de los cuales se superponen. Estos segmentos pueden ser de baldosa y se retira, dejando un pequeño polyomino. Si este pequeño polyomino todavía tiene un agujero, entonces es de tipo 2. Si no, es de tipo 1, ya que tiene el mismo número de blanco y negro de las células.

En ambos casos, cada menor polyomino puede ser en forma de mosaico.