Es posible cubrir una $8 \times8$ junta con $2 \times 1$ piezas?

Question

Tenemos una $8\times 8$ consejo, de color con dos colores como un típico tablero de ajedrez. Ahora, tenemos que quitar dos plazas de color diferente. Es posible la cobertura de la nueva junta directiva con dos fichas de color (es decir, domino piezas)?

Creo que podemos, como después de la eliminación de las dos plazas, nos quedamos con $64-2=62$ plazas con $31$ de los cuadrados de cada color, y a partir de la ficha de dominó cubre dos colores, podemos cubrir la nueva junta directiva con piezas de dominó.

Pero ¿cómo se debe justificar matemáticamente?

Answer 1

Suponer sin pérdida de generalidad que las dos plazas para ser eliminado en diferentes filas. (De lo contrario, gire la placa de 90°).

Primera portada de la junta en horizontal fichas de dominó, y conectar las dos plazas por una línea en zigzag como este:

el que sigue la regla de que si la línea pasa a través de uno de los extremos de un domino, inmediatamente se conecta a otro final. (El requisito de que las dos plazas que tengan diferentes colores asegurar que este será el caso de la final de la ruta, si tan solo empezamos a cabo en la dirección correcta para que esto se sostenga en el principio). Ahora usted puede voltear las fichas de dominó a lo largo de la línea en zigzag para producir una cubierta que evita los dos cuadrados.

---

Con un poco de (fácil)-especial de cubierta para la misma fila caso, esta estrategia puede ser extendido a cualquier tamaño de tablero como una de las longitudes de los lados es par y el otro es $\ge 2$.

Answer 2

A partir de una gráfica de la teoría del punto de vista, esto puede ser visto como un "problema de coincidencia" en un bipartito gráfico.

Los nodos del grafo son los cuadrados restantes.

Dos nodos tienen una arista en el grafo si las plazas son de los vecinos, es decir, si las dos plazas puede ser cubierto por un solo domino.

Obviamente, en cualquier borde, un cuadrado es de color blanco, el otro negro, de ahí el "bipartito" la naturaleza de este gráfico.

Así que usted está tratando de mostrar que hay una perfecta combinación para cualquier gráfico.

En general, existe un teorema acerca de cuando hay una perfecta combinación para un bipartito gráfico, llamado Salón del Teorema o de una Sala del Matrimonio Teorema. Es posiblemente demasiado para esta pregunta - la inducción es, probablemente, el mejor enfoque.

---

Por la discusión sobre Henning la respuesta, en realidad, es posible demostrar su teorema directamente a través de un "ciclo de Hamilton" en el tablero de ajedrez.

Considerar el bucle de ruta de acceso en el tablero:

$$\begin{matrix}1&2&3&4&5&6&7&8\\ 64&15&14&13&12&11&10&9\\ 63&16&17&18&19&20&21&22\\ 62&29&28&27&26&25&24&23\\ 61&30&31&32&33&34&35&36\\ 60&43&42&41&40&39&38&37\\ 59&44&45&46&47&48&49&50\\ 58&57&56&55&54&53&52&51 \end{de la matriz}$$

Así que hemos caminado en círculo, y, si en la parte superior izquierda es de color negro, entonces tenemos que los números impares en negro y los números en blanco.

Si se desenrolla esto, y considero que es de 64 cuentas en un círculo, alternando en blanco y negro, a continuación, si quitamos/cortar uno negro y uno blanco perla, estamos a la izquierda con una cadena de 62 perlas alternando negro/blanco, lo que nos permite cubrir aquellos con fichas de dominó, o dos cadenas separadas.

Con dos cadenas, aquí está la clave: porque cortamos uno negro y uno blanco perla, los dos hebras son de longitud.

Por ejemplo, si hemos quitado la plaza a las 12 y la plaza en la 23, entonces podríamos tener el domino de la colocación: $$(13,14),(15,16),(17,18),(19,20),(21,22), \\(24,25),\dots,(62,63),(64,1),(2,3),(4,5),(6,7),(8,9),(10,11).$$

Esto se puede generalizar como: "Si un bipartito grafo tiene un ciclo Hamiltoniano, entonces si elimina un nodo de cada una de las partes, usted todavía puede obtener un perfecto maridaje."

En particular, este argumento funciona para cualquier $2n\times m$ junta, dado que podemos obtener de un "Rey del ciclo tour" en la junta.

Por ejemplo, $3\times 4$ junta:

$$\begin{matrix} 1 & 2& 3&4\\ 12& 9& 8&5\\ 11&10& 7&6 \end{de la matriz}$$

Answer 3

Sugerencia: Una estrategia prometedora es la de demostrar que la reclamación

Si quitamos dos opuestos-cuadros de colores a partir de una $2m\times 2m$ tablero de ajedrez,
podemos azulejo de la parte restante con $2\times 1$ fichas de dominó.

por inducción en $m$. El caso de $m=1$ es trivial. Suponga que la demanda se mantiene para algunos $m\geq 1$ y considerar la posibilidad de una $(2m+2)\times (2m+2)$ tablero de ajedrez. Si el eliminado las plazas no se encuentran en el límite del tablero de ajedrez, no hay nada que demostrar. Por lo tanto podemos suponer que al menos uno de los quitan plazas se encuentra en el límite. Y también podemos iniciar suelo de baldosas siguiendo una espiral, a partir de la próxima a la quita de la plaza, en el límite:

Otra idea interesante es simplemente colocar $31$ no superposición de fichas de dominó en un $8\times 8$ tablero de ajedrez y empezar a jugar de Sokoban con el dominó, con el fin de liberar la quería plazas.

Answer 4

Completar un enfoque sugerido por Thomas Andrews, si podemos demostrar que en el completo tablero de ajedrez de cualquier correcta subconjunto de los cuadrados blancos tienen más negro de los vecinos que tiene el número de miembros, de la Sala de matrimonio teorema se aplica a un tablero de ajedrez con dos plazas de borrado.

Supongamos por lo tanto, que un subconjunto de los cuadros blancos son dadas. Desde las líneas roja y verde en el siguiente diagrama de conectar todos los cuadrados en blanco, habrá al menos uno rojo o verde de la línea que va de una plaza en el subconjunto a de un cuadrado fuera de ella:

Suponer sin pérdida de generalidad que hay una red de línea de unirse a una plaza en el subconjunto a de un cuadrado fuera del subconjunto. (De lo contrario espejo de todo lo que rodea el blanco de la diagonal).

Ahora el par de cada cuadrado blanco con el negro vecino que está conectado por un azul línea en este diagrama:

Esto le da a uno la vecina cuadrado negro para cada cuadrado blanco. Sin embargo, el cuadrado blanco con una diagonal de la pareja que no seleccionados es, además de vecino a los no seleccionados por el cuadrado negro de la pareja que no es de otra forma utilizado.

Así, como se desee, nuestro conjunto de cuadrados blancos tiene más negro de los vecinos en total que hay en el cuadrado blanco en el conjunto.

Answer 5

Sí.

Considere la junta inicialmente cubierto con fichas de dominó. Después de las dos plazas se han quitado, la junta tiene dos agujeros.

Si los dos agujeros estaban en la misma fila, deslice las fichas de dominó entre los agujeros hasta que uno de los agujeros está lleno. Esto dejará dos agujeros adyacentes que pueden ser cubiertos por un domino.

Si los agujeros están en filas diferentes, deslice el dominó a partir de la fila inferior en la parte superior de la fila hasta hasta que uno de los orificios de llenado. Que sale de la fila inferior con dos agujeros que puede ser llenado como se describió anteriormente.

Si las dos filas adyacentes, deslice la parte superior de la fila a la izquierda o a la derecha hasta su agujero se llena y el agujero se ha movido por encima del agujero en la siguiente fila. Esto puede ser llenado por un domino.