Problema de l'escaquer mutilat
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
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]
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]- ↑ 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.»
- ↑ 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.»
- ↑ 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.»
- ↑ 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.
- ↑ McCarthy, John. «AISB Workshop on Artificial Intelligence and Creativity», 1999. [Consulta: 27 abril 2007]. «Creative Solutions to Problems» (anglès)
- ↑ Watkins, John J. Across the board: the mathematics of chessboard problems. Princeton University Press, 2004, p. 12–14. ISBN 978-0-691-11503-0.
- ↑ 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]- Gamow, George; Stern, Marvin. Puzzle-Math. Viking Press, 1958. ISBN 978-0-333-08637-7.
- Gardner, Martin. My Best Mathematical and Logic Puzzles. Dover, 1994. ISBN 0-486-28152-3.
Enllaços externs
[modifica]
- Dòminos en un tauler de dames, per Jim Loy Arxivat 2013-12-30 a Wayback Machine.
- Dòminos en un tauler de dames Arxivat 2021-03-09 a Wayback Machine.
- Teorema de Gomory per Jay Warendorff.