stringtranslate.com

Problema del tablero de ajedrez mutilado

El tablero de ajedrez mutilado
Solución fallida al problema del tablero de ajedrez mutilado: además de las dos esquinas, quedan sin cubrir dos casillas centrales.

El problema del tablero de ajedrez mutilado es un problema de mosaicos planteado por Max Black en 1946 que plantea la siguiente pregunta:

Supongamos que a un tablero de ajedrez (o damero ) estándar de 8×8 se le quitan dos esquinas diagonalmente opuestas, lo que deja 62 casillas. ¿Es posible colocar 31 fichas de dominó de tamaño 2×1 de modo de cubrir todas estas casillas?

Se trata de un rompecabezas imposible : no existe ninguna ficha de dominó que cumpla estas condiciones. Una prueba de su imposibilidad es el hecho de que, una vez eliminadas las esquinas, el tablero de ajedrez tiene 32 casillas de un color y 30 del otro, pero cada ficha debe cubrir la misma cantidad de casillas de cada color. En términos más generales, si se eliminan dos casillas cualesquiera del tablero de ajedrez, el resto puede ser cubierto por fichas de dominó si y solo si las casillas eliminadas son de colores diferentes. Este problema se ha utilizado como caso de prueba para el razonamiento automático , la creatividad y la filosofía de las matemáticas .

Historia

El problema del tablero de ajedrez mutilado es un ejemplo de mosaico de dominó de cuadrículas y poliominós , también conocidos como "modelos dímeros", una clase general de problemas cuyo estudio en mecánica estadística se remonta al trabajo de Ralph H. Fowler y George Stanley Rushbrooke en 1937. [1] Los mosaicos de dominó también tienen una larga historia de uso práctico en el diseño de pavimentos y la disposición de pisos de tatami . [2]

El problema del tablero de ajedrez mutilado fue propuesto por el filósofo Max Black en su libro Critical Thinking (1946), con una pista sobre la solución basada en el color a su imposibilidad. [3] [4] Se popularizó en la década de 1950 a través de discusiones posteriores de Solomon W. Golomb (1954), [5] George Gamow y Marvin Stern (1958), [6] Claude Berge (1958), [4] [7] y Martin Gardner en su columna de Scientific American " Mathematical Games " (1957). [8]

El uso del problema del tablero de ajedrez mutilado en el razonamiento automatizado proviene de una propuesta para su uso por parte de John McCarthy en 1964. [9] [10] También se ha estudiado en la ciencia cognitiva como un caso de prueba para la percepción creativa, [11] [12] [13] la motivación original de Black para el problema. [3] En la filosofía de las matemáticas , se ha examinado en estudios de la naturaleza de la prueba matemática . [14] [15] [16] [17]

Solución

El rompecabezas es imposible de completar. Una ficha de dominó colocada en el tablero de ajedrez siempre cubrirá una casilla blanca y una casilla negra. Por lo tanto, cualquier conjunto de fichas de dominó colocadas en el tablero cubrirá la misma cantidad de casillas de cada color. Pero dos casillas opuestas tienen el mismo color: ambas negras o ambas blancas. Si se eliminan, habrá menos casillas de ese color y más del otro color, lo que hará que la cantidad de casillas de cada color sea desigual y el tablero sea imposible de cubrir. [8] La misma idea demuestra que no puede existir una teselación de fichas de dominó cuando se eliminan del tablero dos casillas del mismo color (no solo las esquinas opuestas). [18]

También se han encontrado otras pruebas de imposibilidad. Una prueba de Shmuel Winograd comienza con la inducción. En una determinada disposición del tablero, si una fila tiene un número impar de casillas no cubiertas por fichas de dominó verticales de la fila anterior, entonces un número impar de fichas de dominó verticales debe extenderse a la siguiente fila. La primera fila tiene, trivialmente, un número impar de casillas (es decir, 7) no cubiertas por fichas de dominó de la fila anterior. Así, por inducción, cada uno de los siete pares de filas consecutivas alberga un número impar de fichas de dominó verticales, lo que produce un número total impar. Por el mismo razonamiento, el número total de fichas de dominó horizontales también debe ser impar. Como la suma de dos números impares, el número total de fichas de dominó (verticales y horizontales) debe ser par. Pero para cubrir el tablero de ajedrez mutilado, se necesitan 31 fichas de dominó, un número impar. [19] [20] Otro método cuenta los bordes de cada color alrededor del límite del tablero de ajedrez mutilado. Su número debe ser igual en cualquier región del tablero que se pueda enlosar, porque cada ficha tiene tres aristas de cada color y cada arista interna entre fichas de dominó forma pares de límites de colores opuestos. Sin embargo, el tablero de ajedrez mutilado tiene más aristas de un color que del otro. [21]

Teorema de Gomory: si se eliminan dos cuadrados de colores opuestos de un tablero de ajedrez, queda una región que se puede cubrir con fichas de dominó. Los dos cuadrados eliminados dividen un ciclo hamiltoniano a través de los cuadrados en uno (izquierda) o dos (derecha) caminos a través de un número par de cuadrados, lo que permite cubrir el tablero de ajedrez modificado con fichas de dominó colocadas a lo largo de los caminos.
Una región del tablero de ajedrez que no tiene fichas de dominó, pero para la que las pruebas de imposibilidad basadas en colores no funcionan

Si se eliminan dos cuadrados de colores opuestos, entonces el tablero restante siempre puede ser cubierto con fichas de dominó; este resultado es el teorema de Gomory , [22] en honor al matemático Ralph E. Gomory , cuya demostración fue publicada en 1973. [18] [20] El teorema de Gomory puede demostrarse utilizando un ciclo hamiltoniano del gráfico de la 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. Ambos caminos son fáciles de dividir en fichas de dominó si se siguen. [22] El teorema de Gomory es específico para la eliminación de solo un cuadrado de cada color. Eliminar un mayor número de cuadrados, con números iguales de cada color, puede dar como resultado una región que no tiene mosaicos de dominó, pero para la cual las pruebas de imposibilidad basadas en coloración no funcionan. [23]

Aplicación al razonamiento automatizado

Los problemas de teselación de dominó en poliominós , como el problema del tablero de ajedrez mutilado, se pueden resolver en tiempo polinomial , ya sea convirtiéndolos en problemas de teoría de grupos , [21] [24] o como instancias de emparejamiento bipartito . En la última formulación, se obtiene un grafo bipartito con un vértice para cada cuadrado disponible del tablero de ajedrez y una arista para cada par de cuadrados adyacentes; el problema es encontrar un sistema de aristas que toque cada vértice exactamente una vez. Al igual que en la prueba basada en coloración de la imposibilidad del problema del tablero de ajedrez mutilado, el hecho de que este grafo tenga más vértices de un color que del otro implica que no cumple las condiciones necesarias del teorema del matrimonio de Hall , por lo que no existe emparejamiento. [23] [25] [26] El problema también se puede resolver formulándolo como un problema de satisfacción de restricciones y aplicando programación semidefinida a una relajación . [27]

En 1964, John McCarthy propuso el tablero de ajedrez mutilado como un problema difícil para los sistemas de prueba automatizados , formulándolo en lógica de primer orden y pidiendo un sistema que pueda determinar automáticamente la insolubilidad de esta formulación. [9] La mayoría de las consideraciones de este problema proporcionan soluciones "en el sentido conceptual" que no se aplican a la formulación lógica del problema de McCarthy. [28] A pesar de la existencia de métodos generales como los basados ​​en la correspondencia de grafos, es exponencialmente difícil que la resolución resuelva la formulación lógica del problema de McCarthy, [29] [30] [31] destacando la necesidad de métodos en inteligencia artificial que puedan cambiar automáticamente a una representación del problema más adecuada [32] y de sistemas de representación del conocimiento que puedan gestionar las equivalencias entre diferentes representaciones. [10] Las pruebas cortas son posibles utilizando la resolución con variables adicionales, [33] o en sistemas de prueba más fuertes que permiten la expresión de patrones de mosaico evitables que pueden podar el espacio de búsqueda. [34] Los asistentes de prueba de nivel superior son capaces de manejar directamente la prueba de imposibilidad basada en coloración; estos incluyen a Isabelle , [35] el sistema Mizar , [36] y Nqthm . [37]

Problemas relacionados

El problema de la gira de Wazir

Un problema similar pregunta si un wazir que comienza en una esquina de un tablero de ajedrez ordinario puede visitar cada casilla exactamente una vez, y terminar en la esquina opuesta. El wazir es una pieza de ajedrez de hadas que puede moverse solo una casilla vertical u horizontalmente (no diagonalmente). Usando un razonamiento similar a la solución clásica del problema del tablero de ajedrez mutilado, el recorrido de este wazir no existe. Por ejemplo, si la casilla inicial es blanca, como cada movimiento alterna entre casillas blancas y negras, la casilla final de cualquier recorrido completo es negra. Sin embargo, la casilla de la esquina opuesta es blanca. [38] Este tipo de recorrido de un tablero de ajedrez también forma la base de un tipo de rompecabezas llamado Numbrix , que pide un recorrido en el que las posiciones de ciertas casillas coincidan con pistas dadas. [39] La imposibilidad de un recorrido de esquina a esquina muestra la imposibilidad de un rompecabezas Numbrix con las pistas 1 en una esquina y 64 en la esquina opuesta.

El teorema de De Bruijn se refiere a la imposibilidad de empaquetar ciertos cuboides en un cuboide mayor. Por ejemplo, es imposible, según este teorema, llenar una caja de 6 × 6 × 6 con cuboides de 1 × 2 × 4. La prueba utiliza un argumento de coloración del tablero de ajedrez similar al del problema del tablero de ajedrez mutilado. [40]

Referencias

  1. ^ Fowler, RH ; Rushbrooke, GS (1937), "Un intento de extender la teoría estadística de soluciones perfectas", Transactions of the Faraday Society , 33 : 1272, doi :10.1039/tf9373301272
  2. ^ Erickson, Alejandro; Ruskey, Frank ; Schurch, Mark; Woodcock, Jennifer (2010), "Arreglos auspiciosos de tatamis", en tailandés, My T .; Sahni, Sartaj (eds.), Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, 19-21 de julio de 2010, Actas , Lecture Notes in Computer Science, vol. 6196, Springer, págs. 288-297, arXiv : 1103.3309 , doi :10.1007/978-3-642-14031-0_32, ISBN 978-3-642-14030-3, MR  2720105, S2CID  6603662
  3. ^ ab Black, Max (1946), Pensamiento crítico: Introducción a la lógica y al método científico , Prentice Hall, págs. 157, 433
  4. ^ ab Robinson, JA (1991), "Pruebas formales e informales", en Boyer, Robert S. (ed.), Razonamiento automatizado: ensayos en honor a Woody Bledsoe , Automated Reasoning Series, vol. 1, Springer Netherlands, págs. 267–282, doi :10.1007/978-94-011-3488-0_13, ISBN 978-94-010-5542-0; ver especialmente la Sección 13.1, "El problema del tablero de ajedrez mutilado", págs. 271-274 Archivado el 18 de julio de 2022 en Wayback Machine .
  5. ^ Golomb, SW (1954), "Tableros de ajedrez y poliominós", The American Mathematical Monthly , 61 (10): 675–682, doi :10.1080/00029890.1954.11988548, JSTOR  2307321, MR  0067055
  6. ^ Gamow, George ; Stern, Marvin (1958), "Juego de dominó", Puzzle-Math , Viking Press, págs. 87–90, ISBN 978-0-333-08637-7
  7. ^ Berge, Claude (1958), Théorie des graphes et ses apps (en francés), Dunod, p. 176
  8. ^ ab Gardner, Martin (febrero de 1957), "Una variedad de acertijos enloquecedores", Mathematical Games, Scientific American , 196 (2): 152–158, doi :10.1038/scientificamerican0257-152, JSTOR  24941903; para la solución, véase Gardner, Martin (marzo de 1957), "Algunas versiones antiguas y nuevas de tres en raya, además de las respuestas a los acertijos del mes pasado", Mathematical Games, Scientific American , 196 (3): 160–168, doi :10.1038/scientificamerican0357-160, JSTOR  24940785. Reimpreso en My Best Mathematical and Logic Puzzles (Dover Publications, 1994), páginas 2 y 39.
  9. ^ ab McCarthy, John (17 de julio de 1964), Un hueso duro de roer para los procedimientos de prueba, Stanford AI Memo, vol. 16, archivado desde el original el 2021-05-16 , consultado el 2022-07-18
  10. ^ ab Kerber, Manfred; Pollet, Martin (2005), "Un hueso duro de roer para la gestión del conocimiento matemático", en Kohlhase, Michael (ed.), Mathematical Knowledge Management, 4.ª Conferencia Internacional, MKM 2005, Bremen, Alemania, 15-17 de julio de 2005, Documentos revisados ​​seleccionados , Lecture Notes in Computer Science, vol. 3863, Springer, págs. 81–95, doi :10.1007/11618027_6, ISBN 978-3-540-31430-1
  11. ^ Kaplan, Craig A.; Simon, Herbert A. (julio de 1990), "En busca de la introspección", Cognitive Psychology , 22 (3): 374–419, doi :10.1016/0010-0285(90)90008-r, S2CID  54334455
  12. ^ Akin, Ömer; Akin, Cem (enero de 1998), "Sobre el proceso de creatividad en rompecabezas, inventos y diseños", Automation in Construction , 7 (2–3): 123–138, doi :10.1016/s0926-5805(97)00057-5
  13. ^ Bilalić, Merim; Graf, Mario; Vaci, Nemanja; Danek, Amory H. (agosto de 2019), "Cuando la solución está a la vuelta de la esquina: mejor rendimiento en la resolución de problemas, pero menor experiencia de "¡ajá!" para los expertos en ajedrez en el problema del tablero de ajedrez mutilado", Cognitive Science , 43 (8): e12771, doi : 10.1111/cogs.12771 , PMID  31446653
  14. ^ MacKenzie, Donald (2005), "Computación y las culturas de la prueba", Philosophical Transactions of the Royal Society , 363 (1835): 2335–2350, Bibcode :2005RSPTA.363.2335M, doi :10.1098/rsta.2005.1649, JSTOR  30039731, MR  2197653, PMID  16188609, S2CID  18225791
  15. ^ Kerber, Manfred (2014), "Una prueba y algunas representaciones", en Wyatt, Jeremy L.; Petters, Dean D.; Hogg, David C. (eds.), De los animales a los robots y viceversa: reflexiones sobre problemas difíciles en el estudio de la cognición, una colección en honor a Aaron Sloman , Cognitive Systems Monographs, vol. 22, Springer International Publishing, págs. 65–73, doi :10.1007/978-3-319-06614-1_5, ISBN 978-3-319-06613-4
  16. ^ Tanswell, Fenner (2015), "Un problema con la dependencia de las pruebas informales respecto de las pruebas formales", Philosophia Mathematica , Serie III, 23 (3): 295–310, doi :10.1093/philmat/nkv008, MR  3404036
  17. ^ Starikova, Irina; Van Bendegem, Jean Paul (2021), "Revisitando el tablero de ajedrez mutilado o los múltiples roles de un cuadro", Logique et Analyse , 64 (255): 289–312, doi :10.2143/LEA.255.0.3290192, MR  4396339, archivado desde el original el 2022-07-19 , consultado el 2022-07-19
  18. ^ ab Honsberger, R. (1973), "Teorema de Gomory", Gemas matemáticas I , Asociación Matemática de América, págs. 65-67
  19. ^ McCarthy, John (1999), "Soluciones creativas a los problemas", Taller AISB sobre inteligencia artificial y creatividad , archivado desde el original el 23 de octubre de 2018 , consultado el 27 de abril de 2007
  20. ^ ab Mendelsohn, NS (2004), "Mosaicos con fichas de dominó", The College Mathematics Journal , 35 (2): 115–120, doi :10.2307/4146865, JSTOR  4146865Mendelsohn atribuye la publicación original del teorema de Gomory a Honsberger (1973).
  21. ^ ab Propp, Jim (2021), "La influencia de Conway en el estudio de los mosaicos aleatorios", The Mathematical Intelligencer , 43 (2): 40–46, doi :10.1007/s00283-021-10089-3, MR  4278473, S2CID  236397105
  22. ^ ab Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems , Princeton University Press, págs. 12-14, ISBN 978-0-691-11503-0
  23. ^ ab Wright, Colin (2014), "El tablero de ajedrez mutilado (revisitado)" (PDF) , Recreational Mathematics Magazine (1): 4–9, MR  3323392, archivado (PDF) del original el 2022-08-08 , consultado el 2022-07-18
  24. ^ Thurston, William P. (1990), "Grupos de teselación de Conway", The American Mathematical Monthly , 97 (8): 757–773, doi :10.2307/2324578, JSTOR  2324578, MR  1072815
  25. ^ Urquhart, Alasdair (2003), "Pruebas de resolución de principios de correspondencia", Anales de Matemáticas e Inteligencia Artificial , 37 (3): 241–250, doi :10.1023/A:1021231610627, MR  1969128, S2CID  6753523
  26. ^ Codel, Cayden R.; Reeves, Joseph E.; Heule, Marijn JH ; Bryant, Randal E. (2021), "Bipartite perfect matching benchmarks" (PDF) , en Balyo, Tomáš; Froleyks, Nils; Heule, Marijn; Iser, Markus; Järvisalo, Matti; Suda, Martin (eds.), Proceedings of SAT Competition 2021: Solver and Benchmark Descriptions , Serie de informes B del Departamento de Ciencias de la Computación, vol. B-2021-1, Helsinki: Departamento de Ciencias de la Computación, Universidad de Helsinki, pp. 52–53, hdl :10138/333647, archivado (PDF) del original el 2022-07-18 , consultado el 2022-07-18
  27. ^ de Klerk, Etienne; Van Maaren, Hans; Warners, Joost P. (2000), "Relajaciones del problema de satisfacibilidad usando programación semidefinida", Journal of Automated Reasoning , 24 (1–2): 37–65, doi :10.1023/A:1006362203438, MR  1750258, S2CID  5727281, archivado desde el original el 20 de junio de 2021 , consultado el 19 de julio de 2022
  28. ^ Andrews, Peter B.; Bishop, Matthew (1996), "Sobre conjuntos, tipos, puntos fijos y tableros de ajedrez", en Miglioli, Pierangelo; Moscato, Ugo; Mundici, Daniele; Ornaghi, Mario (eds.), Demostración de teoremas con tablas analíticas y métodos relacionados, 5.º taller internacional, TABLEAUX '96, Terrasini, Palermo, Italia, 15-17 de mayo de 1996, Actas , Lecture Notes in Computer Science, vol. 1071, Springer, págs. 1-15, doi :10.1007/3-540-61208-4_1, ISBN 978-3-540-61208-7, archivado desde el original el 18 de julio de 2022 , recuperado el 18 de julio de 2022 , 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
  29. ^ Dantchev, Stefan S.; Riis, Søren (2001), "'Planar' tautologies hard forresolution", 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 de octubre de 2001, Las Vegas, Nevada, EE. UU. , IEEE Computer Society, págs. 220-229, doi :10.1109/SFCS.2001.959896, S2CID  18849777, archivado desde el original el 14 de septiembre de 2022 , consultado el 18 de julio de 2022
  30. ^ Alekhnovich, Michael (2004), "El problema del tablero de ajedrez mutilado es exponencialmente difícil de resolver", Theoretical Computer Science , 310 (1–3): 513–525, doi : 10.1016/S0304-3975(03)00395-5 , MR  2020358
  31. ^ Razborov, Alexander A. (2004), "Límites inferiores de resolución para principios de coincidencia perfecta" (PDF) , Journal of Computer and System Sciences , 69 (1): 3–27, doi :10.1016/j.jcss.2004.01.004, MR  2070797, archivado (PDF) del original el 2022-08-08 , consultado el 2022-07-19
  32. ^ Korf, Richard E. (1980), "Hacia un modelo de cambios de representación", Inteligencia artificial , 14 (1): 41–78, doi :10.1016/0004-3702(80)90033-8, MR  0587851
  33. ^ Krishnamurthy, Balakrishnan (1985), "Pruebas breves para fórmulas complicadas", Acta Informatica , 22 (3): 253–275, doi :10.1007/BF00265682, MR  0806206, S2CID  2459540
  34. ^ Heule, Marijn JH ; Kiesl, Benjamin; Biere, Armin (2019), "Pruebas clausales de tableros de ajedrez mutilados", en Badger, Julia M.; Rozier, Kristin Yvonne (eds.), NASA Formal Methods – 11th International Symposium, NFM 2019, Houston, TX, EE. UU., 7 al 9 de mayo de 2019, Actas , Lecture Notes in Computer Science, vol. 11460, Springer, págs. 204–210, doi :10.1007/978-3-030-20652-9_13, ISBN 978-3-030-20651-2, Número de identificación del sujeto  92989148
  35. ^ Paulson, Lawrence C. (2001), "Una formalización y prueba sencillas para el tablero de ajedrez mutilado" (PDF) , Logic Journal of the IGPL , 9 (3): 475–485, doi :10.1093/jigpal/9.3.475, MR  1828741, archivado (PDF) desde el original el 2022-08-08 , consultado el 2022-07-18
  36. ^ Rudnicki, Piotr (1996), El problema del tablero de ajedrez mutilado en la teoría de conjuntos ligeros de Mizar, Informe técnico, vol. TR96-09, Departamento de Ciencias de la Computación de la Universidad de Alberta, doi :10.7939/R3QV3C738, archivado desde el original el 18 de julio de 2022 , consultado el 18 de julio de 2022
  37. ^ Subramanian, Sakthi (1996), "Una solución interactiva al problema del tablero de ajedrez mutilado", Journal of Logic and Computation , 6 (4): 573–598, doi :10.1093/logcom/6.4.573, MR  1406233
  38. ^ Bivens, Irl C.; Holshouser, Arthur L.; Klein, Benjamin G. (octubre de 2008), "Circuitos Wazir en un tablero de ajedrez obstruido", Mathematics Magazine , 81 (4): 276–284, doi :10.1080/0025570X.2008.11953562, JSTOR  27643123, S2CID  125950546
  39. ^ Hanson, Mary Grace; Nash, David A. (primavera de 2018), "Rompecabezas Numbrix mínimos y máximos", Pi Mu Epsilon Journal , 14 (8): 505–514, arXiv : 1706.09389
  40. ^ de Bruijn, NG (1969), "Rellenar cajas con ladrillos", The American Mathematical Monthly , 76 (1): 37–40, doi :10.2307/2316785, JSTOR  2316785, MR  0234841

Enlaces externos

Wikimedia Commons alberga una categoría multimedia sobre Problema del tablero de ajedrez mutilado .