Problema de l'escaquer mutilat

De la Viquipèdia, l'enciclopèdia lliure
abcdefgh
8
h8 black cross
a1 black cross
8
77
66
55
44
33
22
11
abcdefgh
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 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]

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]

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]

  1. Andrews, Peter B.; Bishop, Matthew. Theorem Proving With Analytic Tableaux and Related Methods: 5th International Workshop, Tableaux '96, Terrasini, Palermo, Italy, 15-17th, 1996, Proceedings. Springer-Verlag, 1996. «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. Bancerek, Grzegorz. QED Workshop, II. Warsaw University, 1995, p. 25–26. «The problem presented by John McCarthy during his lecture "Heavy duty set theory"¹ has been resolved here.» 
  3. Arthan, R. D. «The Mutilated Chessboard Theorem in Z» (PDF), 2005. [Consulta: 6 maig 2007]. «The mutilated chessboard theorem was proposed over 40 years ago by John McCarthy as a “tough nut to crack” for automated reasoning.»
  4. Alekhnovich, Michael «Mutilated chessboard problem is exponentially hard for resolution». Theoretical Computer Science, 310, 1-3, 2004, p. 513–525. DOI: 10.1016/S0304-3975(03)00395-5.
  5. McCarthy, John. «AISB Workshop on Artificial Intelligence and Creativity», 1999. [Consulta: 27 abril 2007]. «Creative Solutions to Problems» (anglès)
  6. Watkins, John J. Across the board: the mathematics of chessboard problems. Princeton University Press, 2004, p. 12–14. ISBN 978-0-691-11503-0. 
  7. Segons Mendelsohn, la publicació original fou al llibre de Honsberger. Mendelsohn, N. S. «Tiling with dominoes». The College Mathematics Journal. Mathematical Association of America, 35, 2, 2004, p. 115–120. DOI: 10.2307/4146865.; Honsberger, R. Mathematical Gems I. Mathematical Association of America, 1973. 

Bibliografia[modifica]

Enllaços externs[modifica]

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