Problema del tablero de ajedrez mutilado

De Wikipedia, la enciclopedia libre
Ir a la navegación Ir a la búsqueda
Chess zhor 26.png
Chess zver 26.png a8 b8 c8 d8 e8 f8 g8 h8 xx Chess zver 26.png
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 xx b1 c1 d1 e1 f1 g1 h1
Chess zhor 26.png
Problema del tablero de ajedrez mutilado

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:

Supóngase que a un tablero de ajedrez estándar de 8×8 se le eliminan dos esquinas diagonalmente opuestas, dejando 62 casillas. ¿Es posible colocar 31 piezas de dominó de tamaño 2×1 recubriendo todo el tablero?

La mayoría de las consideraciones sobre este problema en la literatura relacionada proporcionan soluciones "en el sentido conceptual", pero sin pruebas.[1]John McCarthy lo propuso como un "problema duro" para sistemas de prueba automatizada.[2]​ De hecho, la solución que utiliza el sistema de resolución por inferencia es exponencialmente duro.[3]

Solución[editar]

A mutilated chessboard problem example.
Ejemplo de tablero de ajedrez mutilado, que muestra las casillas vacías en las esquinas (aunque quedan dos plazas negras vacías en el centro)

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.[4]

Teorema de Gomory[editar]

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.[5][6]​ 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ó.

Véase también[editar]

Referencias[editar]

  1. Andrews, Peter B.; Bishop, Matthew (1996), «On Sets, Types, Fixed Points, and Checkerboards», Theorem Proving With Analytic Tableaux and Related Methods: 5th International Workshop, Tableaux '96, Terrasini, Palermo, Italy, 15-17th, 1996, Proceedings, Lecture Notes in Computer Science, Springer-Verlag, «most treatments of the problem in the literature solve it in the conceptual sense, but do not actually provide proofs of the theorem in either of McCarthy's original formulations.» 
  2. Arthan, R. D. (2005), The Mutilated Chessboard Theorem in Z (PDF), consultado el 6 de mayo de 2007, «The mutilated chessboard theorem was proposed over 40 years ago by John McCarthy as a “tough nut to crack” for automated reasoning.» 
  3. Alekhnovich, Michael (2004), «Mutilated chessboard problem is exponentially hard for resolution», Theoretical Computer Science 310 (1-3): 513-525, doi:10.1016/S0304-3975(03)00395-5 .
  4. McCarthy, John (1999), «Creative Solutions to Problems», AISB Workshop on Artificial Intelligence and Creativity, consultado el 27 de abril de 2007 
  5. Watkins, John J. (2004), Across the board: the mathematics of chessboard problems, Princeton University Press, pp. 12–14, ISBN 978-0-691-11503-0 .
  6. According to Mendelsohn, the original publication is in Honsberger's book. Mendelsohn, N. S. (2004), «Tiling with dominoes», The College Mathematics Journal (Mathematical Association of America) 35 (2): 115-120, JSTOR 4146865, doi:10.2307/4146865 ; Honsberger, R. (1973), Mathematical Gems I, Mathematical Association of America .

Bibliografía[editar]

Enlaces externos[editar]