El problema del tablero de ajedrez mutilado es un rompecabezas de enlosado propuesto por el filósofo analítico Max Black en su libro "Critical Thinking" (Pensamiento Crítico) (1946). Fue posteriormente analizado por Solomon W. Golomb (1954), Gamow y Stern (1958) y por Martin Gardner en su columna del Scientific American "Juegos Matemáticos". El problema se plantea como sigue:
La mayoría de las consideraciones sobre este problema en la literatura relacionada proporcionan soluciones "en el sentido conceptual", pero sin pruebas. John McCarthy lo propuso como un "problema duro" para sistemas de prueba automatizada. De hecho, la solución que utiliza el sistema de resolución por inferencia es exponencialmente duro.
El rompecabezas es imposible de completar. Una pieza de dominó colocada sobre el tablero de ajedrez siempre cubrirá una casilla blanca y una negra. Por lo tanto, una colección de piezas de dominó colocada sobre el tablero cubrirá igual número de casillas de cada color. Si se quitan las dos esquinas blancas, entonces quedan 30 casillas blancas y 32 casillas negras para ser cubiertas por las piezas de dominó, lo que resulta imposible. Si se quitan las dos esquinas negras, entonces quedan 32 lugares blancos y 30 negros, así que otra vez es imposible resolver el problema.
La misma prueba de imposibilidad demuestra que no existe un teselado de dominó que recubra el tablero de ajedrez si se retira cualquier pareja de casillas del mismo color. Aun así, si se retiran dos casillas de colores opuestos, entonces siempre es posible recubrir el tablero restante con piezas de dominó. Este resultado se denomina teorema de Gomory y lleva el nombre de su descubridor, el matemático Ralph E. Gomory, que publicó la prueba en 1973. El teorema puede ser probado utilizando un ciclo hamiltoniano de un gráfico de celosía, formado por las casillas del tablero de ajedrez. La extracción de dos casillas de colores opuestos divide este ciclo en dos caminos con un número impar de casillas cada uno, siendo ambos fácilmente divisibles en piezas de dominó.
Escribe un comentario o lo que quieras sobre Problema del tablero de ajedrez mutilado (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)