Problema de l'escaquer mutilat

De Viquipèdia
Dreceres ràpides: navegació, cerca
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 de l'escaquer mutilat.

El problema de l'escaquer mutilat és un puzle proposat pel filòsof Max Black al seu llibre Pensament Crític (1946). Fou estudiat més tard per Solomon W. Golomb (1954), Gamow & Stern (1958) o per Martin Gardner a la seva columna Mathematical Games a la revista Scientific American. El problema és com segueix:

Donat un escaquer estàndard de 8x8 on dues cantonades de la mateixa diagonal han estat tretes, deixant així 62 caselles al tauler. Seria llavors possible de situar-hi 31 peces de dòmino de mida 2x1 caselles, de tal manera que es cobrissin totes les caselles?

La majoria de consideracions sobre aquest problema a la literatura existent es dirigeixen a solucions «en el sentit conceptual» sense proves.[1] John McCarthy va proposar-lo[2] com a un problema difícil per a sistemes de prova automatitzada.[3] De fet, la seva solució fent servir un sistema de resolució d'inferència és exponencialment difícil.[4]

Solució[modifica | modifica el codi]

El puzle és impossible de completar. Una fitxes de dòmino situada sobre l'escaquer sempre cobrirà una casella blanca i una altra de negra. Per tant, una sèrie de fitxes de dòmino situades sobre el tauler sempre cobriran un nombre igual de caselles de cada color. Si s'eliminen les dues cantonades blanques, llavors quedaran 30 caselles blanques i 32 de negres, i per tant, és impossible de cobrir-les. Si s'eliminessin les dues cantonades negres, llavors quedarien 32 caselles blanques i 30 de negres, cosa que faria novament impossible de cobrir-les.[5]

Un exemple de problema de tauler d'escacs mutilat.
Exemple de tauler d'escacs mutilat mostrant les caselles negres buides al centre.

Teorema de Gomory[modifica | modifica el codi]

La mateixa prova d'impossibilitat mostra que no hi ha cap enrajolat de dòmino possible en cap cas si hom lleva dues caselles blanques del tauler. De tota manera, si s'eliminen dues caselles de colors oposats, llavors serà sempre possible d'enrajolar la resta del tauler amb fitxes de dòmino; aquest resultat és anomenat teorema de Gomory,[6] i rep el seu nom del matemàtic Ralph E. Gomory, la prova del qual fou publicada el 1973.[7] El teorema de Gomory pot ser demostrat fent servir el camí hamiltonià del gràfic de graella format per les caselles de l'escaquer; treure dues caselles del mateix color trenca el cicle en dues parts amb un nombre imparell de caselles cadascuna, i ambdues són fàcils de partir en dòminos.

Notes i referències[modifica | modifica el codi]

  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, <http://citeseer.ist.psu.edu/87819.html>
  2. Bancerek, Grzegorz (1995), "The Mutilated Chessboard Problem—checked by Mizar", in Boyer, Robert & Trybulec, Andrzej, QED Workshop, II, Warsaw University, pàg. 25–26, <http://citeseer.ist.psu.edu/87819.html>
  3. Arthan, R. D. (2005), The Mutilated Chessboard Theorem in Z, <http://www.lemma-one.com/ProofPower/examples/wrk071.pdf>. Consultat el 6 maig 2007
  4. 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.
  5. McCarthy, John (1999), "Creative Solutions to Problems", AISB Workshop on Artificial Intelligence and Creativity, <http://www-formal.stanford.edu/jmc/creative/creative.html>. Consultat el 27/4/2007 (anglès)
  6. Watkins, John J. (2004), Across the board: the mathematics of chessboard problems, Princeton University Press, pàg. 12–14, ISBN 978-0-691-11503-0.
  7. Segons Mendelsohn, la publicació original fou al llibre de Honsberger. Mendelsohn, N. S. (2004), "Tiling with dominoes", The College Mathematics Journal (Mathematical Association of America) 35 (2): 115–120, DOI 10.2307/4146865; Honsberger, R. (1973), Mathematical Gems I, Mathematical Association of America.

Bibliografia[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Problema de l'escaquer mutilat Modifica l'enllaç a Wikidata