Máxima de suelo de baldosas sin ninguna 3-en-un-filas

Question

Se le da una forma arbitraria de gran cuadrícula, donde cada cuadrado puede estar apagado o encendido (piensa en el Juego de la vida tipo de junta).

Usted necesita para el azulejo tal una cuadrícula para maximizar el número de "en" plazas sin que haya 3-en-una-fila de "en" plazas. Un 3-en-una-fila puede ser horizontal, vertical o diagonal. 3-en-una-fila de "off" plazas están permitidos.

El mejor suelo de baldosas que se me ocurrió es

101010101010
101010101010
010101010101
010101010101

lo que da una proporción de 1/2. La mejor cota superior de la que tengo es 6/9 (como usted no puede caber 7 en cualquiera de no-ajuste cuadrado de 3x3). Creo que la solución óptima será periódica, pero si no es así entonces que está bien.

Es el mosaico por encima del óptimo de ordenamiento en teselas? Puede que este problema se pueden generalizar a N-en-una-fila?

Answer 1

Usted puede lograr 5/9 de la densidad infinitamente suelo de baldosas este patrón horizontal:

010101
110110
101010

Sin embargo, esto no azulejo el avión.

También hice una búsqueda exhaustiva de 3x6, y se encontró que 10/18 fue óptimo. Cualquier mosaico del plano con una mayor densidad de 10/18 debe contener bloques de 3x6 con más de 10 plazas. Esto es imposible, por lo tanto 5/9 es un límite superior en la densidad.

EDIT: La mejor enlazado he encontrado a través de la búsqueda exhaustiva es 13/24. No hay mejor densidad es posible.

Sin embargo @feersum conjeturó que para cualquier tamaño finito de campo $n+1 \over 2n$ es siempre posible, lo que si es cierto, hace que la búsqueda exhaustiva de un infructuoso esfuerzo para demostrar que el obligado 1/2 ajustados.

Answer 2

El límite superior puede ser mejorado considerablemente mirando 13x13 cuadrados, donde la mejor posible patrón es de 86, lo que da una cota superior de 86/169 $\approx$ 0.5088

Edit: y un poco más con 15x15, que dan 114/225 $\approx$ 0.5067

Answer 3

Un límite superior de $7/12$ desde la consideración de $3\times4$ rectángulos.
Si hay ocho luces, a continuación, cada uno de los cuatro columnas tiene dos luces. Sólo hay un par de maneras para llenar el medio de las dos columnas, y cada uno de ellos impide que muchas luces en el exterior de las columnas.
Siete de los 12 que se pueden hacer (pero no se extiende a una desenfrenada matriz):
1010
1011
0101

Answer 4

Óptima o no óptima, periódicas o no periódicas, hay esencialmente sólo una manera de hacer esto.

Supongamos que tenemos una asignación de 0s y 1s para cada celda de la cuadrícula infinita, no necesariamente un suelo de baldosas (es decir. no necesariamente periódico), y no necesariamente óptima. El truco es jugar una especie de Sudoku para mostrar que no es una esencia única manera de hacer esto.

Debe haber un 1 en algún lugar en la red. Ahora, a la derecha de este 1, tenemos tres posibilidades: o tenemos 0 0, 0 1, o 1 0. Observe que el caso 1, el 0 es isomorfo al caso 0 0, ya que en el caso anterior tendríamos 1 1 0 y en el segundo nos habría 1 0 0, que son la misma cosa, en virtud de la simetría de un tirón la junta horizontal y el intercambio de 0s y 1s. Así que sólo tenemos dos casos: 1 0 0 y 1 0 1.

En primer lugar, imaginemos que hay un 1 0 0 en algún lugar de la junta. Tenemos otro caso de estudio: la célula inmediatamente bajo es 1, o es 0. Te voy a mostrar cómo se puede utilizar el "sudoku" para obtener una contradicción de la primera suposición:

1 0 0     1 0 0    1 0 0    1 0 0
1      -> 1     -> 1 1   -> 1 1 0   Contradiction!
          0        0        0   0

Si la celda inmediatamente bajo es 0, entonces tenemos el patrón

1 0 0
0

Si tratamos de aplicar el sudoku método para deducir el resto de la red, nos encontramos con que no podemos ejecutar en cualquier contradicciones, y de hecho podemos comenzar a generar una infinitamente mosaico patrón:

1 1 0 0
0 0 1 1

Usted puede demostrar que si la cuadrícula contiene este 2x3 patrón, y no hay ninguna de la tres-en-una-filas, entonces este patrón debe azulejo infinitamente en todas las direcciones. Esto completa el estudio de caso para cuando la cuadrícula contiene un 1 0 0.

Ahora supongamos que tenemos un 1 0 1 en algún lugar de la red. De nuevo, tenemos que hacer un estudio de caso: hemos

1 0 1
0

o

1 0 1
1

En cualquier caso, el cálculo de ida como de costumbre, bastante encontrar rápidamente el fatal 2x6 patrón mencionado anteriormente (posiblemente girado 90°), así que es eso.