Cubrir un tablero de ajedrez con $2$ plazas perdidas con $31$ dominó

Question

Estoy leyendo un libro destinado a un público amplio (y no sólo a matemáticos, etc.), el libro trata, por supuesto, de matemáticas (todavía no está todavía no está claro de qué se trata exactamente, sólo estoy en la página $2$ ).

El autor propone el siguiente acertijo:

Tome un $8\times8$ aburrido, y quitar la pieza inferior derecha y la superior izquierda, se puede cubrir con $31$ ¿dominó?

La respuesta está dada: es no. El autor explica que si se pintar el tablero como un tablero de ajedrez entonces las piezas retiradas son de del mismo color, pero como cada ficha de dominó cubrirá exactamente una pieza negra una pieza negra y una pieza blanca, no podemos cubrir el $30$ piezas blancas y $32$ piezas negras.

A continuación, el autor plantea un ejercicio:

Demostrar que esto se puede hacer si las piezas retiradas son de diferente color

No sé cómo empezar con esto, puedo mirar una tabla dada y tratar de abarcarlo, pero no puedo dar una metodología o una prueba para esto.

¿Puede alguien indicarme la dirección correcta?

Answer 1

Dibuja un ciclo hamiltoniano en el tablero de ajedrez. Cualquier ciclo servirá, y el siguiente es suficiente:

Elige (cualquier) casilla y llámala $s_0$ . Numerar las siguientes casillas en el ciclo hamiltoniano $s_1, s_2,\ldots s_{63}$ :

Tenga en cuenta que el par $s_i$ son todos de un color (digamos rosa) y el impar $s_i$ son del otro color (digamos marrón). Hasta aquí todo es muy fácil.

Supongamos ahora que se han eliminado dos cuadrados de colores opuestos; por ejemplo:

El ciclo se ha cortado en dos caminos, ambos tienen una longitud uniforme . Este camino se cubre fácilmente con fichas de dominó: digamos que un camino es $s_k, s_{k+1}, \ldots, s_{k+2j+1}$ donde los subíndices se entienden mod 64. Entonces las fichas de dominó pasan fácilmente a $(s_k, s_{k+1}), (s_{k+2}, s_{k+3}), \ldots (s_{k+2j}, s_{k+2j+1})$ . Del mismo modo, el otro camino está embaldosado por $(s_{k+2j+3}, s_{k+2j+4}), \ldots, (s_{k-3}, s_{k-2})$ .

Este teorema y la prueba que he dado aparecen en las páginas 111-112 de Solomon W. Golomb Polyominoes (ed. revisada), Princeton University Press, 1994. La prueba se atribuye a Ralph Gomory .

Answer 2

Considera el rectángulo con los dos cuadrados eliminados en las esquinas diagonalmente opuestas. Demuestra que tiene un lado de longitud par y el otro de longitud impar. Encuentre un patrón estándar para embaldosar tales rectángulos con esquinas diagonalmente opuestas que faltan.

A continuación, demuestre que puede embaldosar el resto del tablero fuera del rectángulo. Puede considerar casos para la paridad de la fila/columna de la posición de una de las esquinas del rectángulo y, de nuevo, mostrar que el exterior se puede embaldosar utilizando uno de un pequeño número de patrones estándar en función de la paridad.

Answer 3

Si son de diferentes colores, entonces empiezas a cubrir el tablero, fila tras fila, hasta llegar a una fila que tenga una casilla vacía. Junto a ella colocas la pieza de dominó en horizontal y sigues compensando hasta llegar a la siguiente fila que tiene el cuadrado que falta.

Ahora tienes que ocuparte de que las piezas que faltan estén en la última fila y lo haces dando la vuelta al tablero.

Answer 4

No es una prueba completa, pero esencialmente esos son los pasos:

• Comprueba que el gráfico de la cuadrícula correspondiente del tablero de ajedrez es hamiltoniano. (En términos sencillos: Tomando sólo los pasos horizontales y verticales se pueden pasar todas las $64$ cuadrados exactamente una vez y termina donde empezó).

• Si se eliminan dos piezas, el círculo se divide en dos caminos, cuyas longitudes son ambas pares, si las piezas eliminadas tienen colores diferentes.

• Como la longitud es uniforme y los caminos sólo tienen pasos horizontales y verticales, se pueden cubrir ambos caminos con fichas de dominó.

Answer 5

Esto puede ser un camino diferente a las respuestas existentes. Usted está buscando un la combinación perfecta en el gráfico de la cuadrícula que corresponde al tablero de ajedrez mutilado. Este grafo es bipartito, por lo que Teorema de Hall da una condición necesaria y suficiente para la existencia de una coincidencia. Esa condición en este contexto sería que para cada subconjunto $S$ de cuadros negros, si $|S|\leq |N(S)|$ donde $N(S)$ es el conjunto de casillas blancas adyacentes a todas las casillas negras de $S$ y viceversa. Creo que esto se puede demostrar sin demasiada dificultad por inducción.