¿Se sabe si las franjas no se pueden baldosar aperiódicamente con una sola baldosa?

Question

Hasta donde yo sé, es un problema de si existe una única conectado azulejo que los azulejos de que el avión no sólo periódicamente.

Es la situación diferente para una tira? (O, para el caso, una tira por la mitad, o cuadrante, o tira doblada.) Quiero decir, ¿es posible que una sola baldosa a baldosa una tira que no sólo periódicamente (o la mitad de la tira, cuadrante, tira doblada), o es también desconocido?

(Pido en general, pero soy particular interesado en los azulejos que son polyominoes.)

Para dar un poco de contexto: estoy en un auto-estudio de la aventura de polyominoes y sus mosaicos, especialmente (me hicieron algunas preguntas anteriores que llegó en este contexto: ¿cada domino mosaico de tener al menos dos "expuestos" fichas de dominó? y Lo rectángulos puede un conjunto de rectángulos de baldosa?). Esta última viene de intentar a ver que tiras (y la mitad de las tiras, etc.) un polyomino puede azulejo. Una forma de hacerlo sería mostrar que usted no puede formar parte de cualquier paralelogramo, como* pedazos que se pueden unir varias veces para formar la tira (o la mitad de las tiras, etc.) Pero esto sólo funcionará si tiras (etc.) siempre puede ser ajustada periódicamente en todo caso.

(*) De paralelogramo, como pieza = una pieza que tiene cuatro lados"; dos opuestos que son rectas y de la misma longitud, y los otros dos no necesariamente recta, pero la onbe es una traducción de la otra. Para polyominoes, figuras donde todas las filas tienen el mismo número de células, y todos ellos son de la fila-conectado. (También he pedido que aquí si hay un plazo para tales polyominoes: hay una palabra para un polyomino con $n$ conectado celdas en cada fila?. Yo no obtener una respuesta, y después de buscar a través de cientos de papeles no he encontrado uno.) Aquí están algunos ejemplos.

(Claramente se puede poner junto a la teja una tira).

Answer 1

Para Wang azulejos y polyominoes: si un azulejo conjunto de azulejos de una tira, existe un periódico de mosaico de la tira por el tile set.

El argumento que sigue es aproximadamente desde el enlace proporcionado por Gerry Meyerson: https://lipn.univ-paris13.fr/GDR-IM-2016/SLIDES/jeandel.pdf

A pesar de que no se ocupan de este tema específicamente que está implícito en cómo su algoritmo funciona.

Voy a hacer que el argumento de polyominoes, pero debe quedar claro que funciona para Wang azulejos y toda una variedad de otras teselas.

Para cualquier franja de suelo de baldosas, se puede cortar hasta el suelo de baldosas en nueva vertical de las baldosas, como se muestra en esta imagen:

Aquí, el original de mosaico conjunto es L-tetrominoes por, y el nuevo vertical azulejos son las tiras delineado en negro.

Esto nos dará un azulejo nuevo conjunto $T_1, \cdots, T_k$, que es finito. Tenemos que tener cuidado de que los azulejos de que la corte polyominoes en diferentes partes son distintas. Por ejemplo, aunque las cuatro fichas que se muestra aquí es el mismo, deben ser diferentes.

Esto nos permite hacer un grafo dirigido con los nuevos azulejos como vértices, y un borde de $T_i$ $T_j$si la colocación de $T_j$ a la derecha es una persona jurídica teniendo en cuenta la configuración de las piezas originales. Por ejemplo, en la figura anterior, si etiquetamos a los azulejos $T_1, \cdots, T_4$, luego tenemos a $T_1 \rightarrow T_2 \rightarrow T_3 \rightarrow T_4 \rightarrow T_1$, pero no por ejemplo a $T_1 \rightarrow T_3$, ya que este "deja un pedazo de algunos azulejos de la serie original".

Para una franja de suelo de baldosas a existir, debe ser posible visitar los nodos siguiendo los bordes de un camino infinito. Pero el número de vértices es finito, para ello debemos tener un ciclo. Y cualquier ciclo significa que podemos construir un periódico de mosaico utilizando los nuevos azulejos, que corresponde a un examen periódico del mosaico de azulejos originales.