El problema del tablero de ajedrez mutilado es un rompecabezas propuesto por el filósofo Max Black en su libro Critical Thinking (1946). Más tarde fue discutido por Solomon W. Golomb (1954), Gamow & Stern (1958) y por Martin Gardner en su columna Scientific American " Mathematical Games ". El problema es el siguiente:
Suponga que un tablero de ajedrez estándar de 8 × 8 tiene dos esquinas diagonalmente opuestas eliminadas, dejando 62 cuadrados. ¿Es posible colocar 31 fichas de dominó de tamaño 2 × 1 para cubrir todos estos cuadrados?
La mayoría de las consideraciones de este problema en la literatura proporcionan soluciones "en el sentido conceptual" sin pruebas. [1] John McCarthy lo propuso como un problema difícil para los sistemas de prueba automatizados . [2] De hecho, su solución utilizando el sistema de resolución de inferencia es exponencialmente difícil. [3]
Solución
El rompecabezas es imposible de completar. Una ficha de dominó colocada en el tablero de ajedrez siempre cubrirá un cuadrado blanco y un cuadrado negro. Por lo tanto, una colección de fichas de dominó colocada en el tablero cubrirá un número igual de casillas de cada color. Si se quitan las dos esquinas blancas del tablero, quedan 30 casillas blancas y 32 casillas negras por cubrir con dominó, por lo que esto es imposible. Si en su lugar se eliminan las dos esquinas negras, quedan 32 cuadrados blancos y 30 cuadrados negros, por lo que nuevamente es imposible. [4]
Término análogo
Un problema similar pregunta si una hormiga que comienza en un cuadrado de la esquina de un tablero de ajedrez sin mutilar puede visitar cada cuadrado exactamente una vez y terminar en el cuadrado de la esquina opuesta. Los movimientos diagonales están prohibidos; cada movimiento debe ser a lo largo de una base.
Usando el mismo razonamiento, esta tarea es imposible. Por ejemplo, si el cuadro inicial es blanco, ya que cada movimiento alterna entre cuadros blancos y negros, el cuadro final de cualquier recorrido completo es negro. Sin embargo, el cuadrado de la esquina opuesta es blanco. [5]
Teorema de gomory
Eliminar un cuadrado negro y uno blanco en este ciclo hamiltoniano (los ejemplos se muestran con ×) produce una (A) o dos (B) trayectorias con números pares de cuadrados |
La misma prueba de imposibilidad muestra que no existe un mosaico de dominó cada vez que se eliminan dos cuadrados blancos del tablero de ajedrez. Sin embargo, si se eliminan dos casillas de colores opuestos, siempre es posible enlosar el tablero restante con fichas de dominó; este resultado se llama teorema de Gomory , [6] y lleva el nombre del matemático Ralph E. Gomory , cuya demostración se publicó en 1973. [7] El teorema de Gomory se puede probar usando un ciclo hamiltoniano del gráfico de cuadrícula formado por los cuadrados del tablero de ajedrez; la eliminación de dos cuadrados de colores opuestos divide este ciclo en dos caminos con un número par de cuadrados cada uno, los cuales son fáciles de dividir en dominós.
Ver también
- Mosaico de un rectángulo con tetrominós
- Teorema de De Bruijn : ejemplo de empaquetar una caja de 6 × 6 × 6 con cuboides de 1 × 2 × 4
- Rompecabezas de Slothouber-Graatsma
Notas
- ^ Andrews, Peter B .; Bishop, Matthew (1996), "Sobre conjuntos, tipos, puntos fijos y tableros de ajedrez", Demostración de teoremas con cuadros analíticos y métodos relacionados: 5º Taller Internacional, Tableaux '96, Terrasini, Palermo, Italia, 15-17 de 1996, Actas , Lecture Notes in Computer Science, Springer-Verlag, la
mayoría de los tratamientos del problema en la literatura lo resuelven en el sentido conceptual, pero en realidad no proporcionan pruebas del teorema en ninguna de las formulaciones originales de McCarthy.
- ^ Arthan, RD (2005), The Mutilated Chessboard Theorem in Z (PDF) , recuperado 2007-05-06 ,
El teorema mutilado del tablero de ajedrez fue propuesto hace más de 40 años por John McCarthy como un "hueso duro de roer" para el razonamiento automatizado.
- ^ Alekhnovich, Michael (2004), "El problema del tablero de ajedrez mutilado es exponencialmente difícil de resolver", Informática teórica , 310 (1-3): 513-525, doi : 10.1016 / S0304-3975 (03) 00395-5.
- ^ McCarthy, John (1999), "soluciones creativas a problemas", AISB Taller sobre Inteligencia Artificial y la creatividad , recuperada 2007-04-27
- ^ Miodrag Petkovic, Matemáticas y ajedrez: 110 entretenidos problemas y soluciones , ISBN 0-486-29432-3
- ^ Watkins, John J. (2004), En general: las matemáticas de los problemas del tablero de ajedrez , Princeton University Press, págs. 12-14 , ISBN 978-0-691-11503-0.
- ↑ Según Mendelsohn, la publicación original está en el libro de Honsberger. Mendelsohn, NS (2004), "Tiling with dominó", The College Mathematics Journal , Mathematical Association of America, 35 (2): 115-120, doi : 10.2307 / 4146865 , JSTOR 4146865; Honsberger, R. (1973), Gemas Matemáticas I , Asociación Matemática de América.
Referencias
- Gamow, George ; Stern, Marvin (1958), Puzzle-Math , Viking Press, ISBN 978-0-333-08637-7
- Gardner, Martin (1994), Mis mejores acertijos matemáticos y lógicos , Dover, ISBN 0-486-28152-3
enlaces externos
- Dominó en un tablero de ajedrez por Jim Loy
- Dominó en un tablero de ajedrez
- Teorema de Gomory de Jay Warendorff, The Wolfram Demonstrations Project .