El problema de lescaquer 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), 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. John McCarthy va proposar-lo com un problema difícil per a sistemes de prova automatitzada. De fet, la seva solució fent servir un sistema de resolució d'inferència és exponencialment difícil.
Solució 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. miniatura|esquerra|alt=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 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, i rep el seu nom del matemàtic Ralph E. Gomory, la prova del qual fou publicada el 1973.Segons Mendelsohn, la publicació original fou al llibre de Honsberger. ; 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
Bibliografia
Enllaços externs
Dòminos en un tauler de dames, per Jim Loy Dòminos en un tauler de dames Teorema de Gomory per Jay Warendorff.
Categoria:Problemes d'escacs i matemàtica