# Mutilated chessboard problem

Mutilated chessboard problem (Redirected from Gomory's theorem) Jump to navigation Jump to search The mutilated chessboard Unsuccessful solution to the mutilated chessboard problem: as well as the two corners, two center squares remain uncovered The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks: Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?

It is an impossible puzzle: there is no domino tiling meeting these conditions. One proof of its impossibility uses the fact that, with the corners removed, the chessboard has 32 squares of one color and 30 of the other, but each domino must cover equally many squares of each color. De forma geral, dominoes can cover all but two squares of the chessboard, if and only if the two uncovered squares are of different colors. This problem has been used as a test case for automated reasoning, creativity, and the philosophy of mathematics.

Conteúdo 1 História 2 Solution 3 Application to automated reasoning 4 Related problems 5 Referências 6 External links History The mutilated chessboard problem is an instance of domino tiling of grids and polyominoes, also known as "dimer models", a general class of problems whose study in statistical mechanics dates to the work of Ralph H. Fowler and George Stanley Rushbrooke in 1937.[1] Domino tilings also have a long history of practical use in pavement design and the arrangement of tatami flooring.[2] The mutilated chessboard problem itself was proposed by philosopher Max Black in his book Critical Thinking (1946), with a hint at the coloring-based solution to its impossibility.[3][4] It was popularized in the 1950s through later discussions by Solomon W. Golomb (1954),[5] Gamow & Stern (1958),[6] Claude Berge (1958),[4] and by Martin Gardner in his Scientific American column "Jogos Matemáticos" (1957).[7] The use of the mutilated chessboard problem in automated reasoning stems from a proposal for its use by John McCarthy in 1964.[8] It has also been studied in cognitive science as a test case for creative insight,[9][10][11] Black's original motivation for the problem.[3] In the philosophy of mathematics, it has been examined in studies of the nature of mathematical proof.[12][13][14][15] Solution The puzzle is impossible to complete. A domino placed on the chessboard will always cover one white square and one black square. Portanto, a collection of dominoes placed on the board will cover an equal numbers of squares of each color. If the two white corners are removed from the board then 30 white squares and 32 black squares remain to be covered by dominoes, so this is impossible. If the two black corners are removed instead, então 32 white squares and 30 black squares remain, so it is again impossible.[16] The same impossibility proof shows that no domino tiling exists whenever any two squares of the same colour (not just the corners) are removed from the chessboard.[17] Several other proofs of impossibility have also been found. For instance a proof by Shmuel Winograd observes that, by induction, in any domino tiling, each row of the mutilated chessboard has an odd number of squares that are not covered by vertical dominoes from the previous row, and therefore an odd number of vertical dominoes must extend into the next row. Desta forma, each of the seven consecutive pairs of rows has an odd number of vertical dominoes, producing an odd total number. By the same reasoning, the total number of horizontal dominoes must also be odd. As the sum of two odd numbers, the total number of dominoes must be even. Mas, to cover the mutilated chessboard, 31 dominoes are needed, an odd number.[16][18] Another method counts the edges of each color around the boundary of the mutilated chessboard. Their numbers must be equal in any tileable region of the chessboard, because each domino has three edges of each color, and each internal edge between dominoes pairs off boundaries of opposite colors. No entanto, the mutilated chessboard has more edges of one color than the other.[19] A B Removing one black and one white square on this Hamiltonian cycle (examples shown with ×) yields one (UMA) or two (B) paths with even numbers of squares If two squares of opposite colors are removed, then it is always possible to tile the remaining board with dominoes; this result is called Gomory's theorem,[20] and is named after mathematician Ralph E. Gomory, whose proof was published in 1973.[17][18] Gomory's theorem can be proven using a Hamiltonian cycle of the grid graph formed by the chessboard squares. The removal of any two oppositely colored squares splits this cycle into two paths with an even number of squares each. Both of these paths are easy to partition into dominoes.[20] Gomory's theorem is specific to the removal of only one square of each color. Removing larger numbers of squares, with equal numbers of each color, can result in a region that has no domino tiling, but for which coloring-based impossibility proofs do not work.[21] Application to automated reasoning Domino tiling problems on polyominoes, such as the mutilated chessboard problem, can be solved in polynomial time, either by converting them into problems in group theory[19][22] or as instances of bipartite matching. In the bipartite matching formulation, one obtains a bipartite graph with a vertex for each available chessboard square and an edge for every pair of adjacent squares; the problem is to find a system of edges that touches each vertex exactly once. As in the coloring-based proof of the impossibility of the mutilated chessboard problem, the fact that this graph has more vertices of one color than the other implies that it fails the necessary conditions of Hall's marriage theorem and that no matching exists.[21][23][24] The problem can also be solved by formulating it as a constraint satisfaction problem, and applying semidefinite programming to a relaxation.[25] Dentro 1964, John McCarthy proposed the mutilated chessboard problem as a hard problem for automated proof systems, formulating it in first-order logic and asking for a system that can automatically determine the unsolvability of this formulation.[8] Most considerations of this problem in the literature provide solutions "in the conceptual sense" that do not apply to McCarthy's logic formulation of the problem.[26] Despite the existence of general methods such as those based on graph matching, finding a solution to a logical formulation of the mutilated chessboard problem using the resolution system of inference is exponentially hard,[27][28][29] highlighting the need for methods in artificial intelligence that can automatically change to a more suitable problem representation.[30] Short proofs are possible using resolution with additional variables,[31] or in stronger proof systems allowing the expression of additional constraints on local patterns of dominoes that can safely be avoided in any tiling and used to prune the search space.[32] Higher-level proof assistants are capable of handling the coloring-based impossibility proof directly; these include, por exemplo, Isabelle,[33] the Mizar system,[34] and Nqthm.[35] Related problems Wazir's tour problem A similar problem asks if a wazir starting at a corner square of an unmutilated chessboard can visit every square exactly once, and finish at the opposite corner square. The wazir is a fairy chess piece that can only move one square vertically or horizontally; diagonal moves are not allowed. Using the same reasoning, this wazir's tour does not exist. Por exemplo, if the initial square is white, as each move alternates between black and white squares, the final square of any complete tour is black. No entanto, the opposite corner square is white.[36] This sort of tour of a chessboard also forms the basis of a type of puzzle called Numbrix, in which one must find a tour in which the positions of certain squares match given clues. The impossibility of a corner-to-corner tour shows that a Numbrix puzzle with the clues 1 in one corner and 64 in the opposite corner has no solution.[37] De Bruijn's theorem concerns the impossibility of packing certain cuboids into a larger cuboid. Por exemplo, it is impossible, according to this theorem, to fill a 6 × 6 × 6 box with 1 × 2 × 4 cuboids. The proof uses a similar chessboard-coloring argument to the mutilated chessboard problem.[38] References ^ Fowler, R. H.; Rushbrooke, G. S. (1937), "An attempt to extend the statistical theory of perfect solutions", Transactions of the Faraday Society, 33: 1272, doi:10.1039/tf9373301272 ^ Erickson, Alejandro; Ruskey, Franco; Schurch, Marca; Woodcock, Jennifer (2010), "Auspicious tatami mat arrangements", in Thai, My T.; Sahni, Sartaj (ed.), Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, Julho 19-21, 2010. Processos, Notas de aula em Ciência da Computação, volume. 6196, Springer, pp. 288-297, arXiv:1103.3309, doi:10.1007/978-3-642-14031-0_32, MR 2720105 ^ Saltar para: a b Black, Máx. (1946), Critical Thinking: An Introduction To Logic And Scientific Method, Prentice Hall, p. 157, 433 ^ Saltar para: a b Robinson, J. UMA. (1991), "Formal and Informal Proofs", in Boyer, Robert S. (ed.), Automated Reasoning: Essays in Honor of Woody Bledsoe, Automated Reasoning Series, volume. 1, Springer Netherlands, pp. 267-282, doi:10.1007/978-94-011-3488-0_13; see especially Section 13.1, "The mutilated chess board problem", pp. 271-274. ^ Golomb, S. C. (1954), "Checker boards and polyominoes", O American Mathematical Monthly, 61: 675–682, doi:10.1080/00029890.1954.11988548, JSTOR 2307321, MR 0067055 ^ Gamow, Jorge; Stern, Marvin (1958), "Domino game", Puzzle-Math, Viking Press, ISBN 978-0-333-08637-7 ^ Gardner, Martinho (Fevereiro 1957), "An assortment of maddening puzzles", Jogos Matemáticos, Americano científico, 196 (2): 152-158, JSTOR 24941903; for solution, see Gardner, Martinho (Marchar 1957), "Some old and new versions of ticktacktoe, plus the answers to last month's puzzles", Jogos Matemáticos, Americano científico, 196 (3): 160–168, JSTOR 24940785 ^ Saltar para: a b McCarthy, John (Julho 17, 1964), A tough nut for proof procedures, Stanford AI Memo, volume. 16 ^ Kaplan, Craig A.; Simão, Herbert A. (Julho 1990), "In search of insight", Cognitive Psychology, 22 (3): 374–419, doi:10.1016/0010-0285(90)90008-r ^ Akin, Ömer; Akin, Cem (Janeiro 1998), "On the process of creativity in puzzles, inventions, and designs", Automation in Construction, 7 (2-3): 123-138, doi:10.1016/s0926-5805(97)00057-5 ^ Bilalić, Merim; Graf, Mario; Vaci, Nemanja; Danek, Amory H. (Agosto 2019), "When the solution is on the doorstep: Better solving performance, but diminished aha! experience for chess experts on the mutilated checkerboard problem", Cognitive Science, 43 (8), doi:10.1111/cogs.12771 ^ MacKenzie, Donald (2005), "Computing and the cultures of proving", Transações Filosóficas da Royal Society, 363 (1835): 2335–2350, doi:10.1098/rsta.2005.1649, JSTOR 30039731, MR 2197653 ^ Kerber, Manfred (2014), "A proof and some representations", in Wyatt, Jeremy L.; Petters, Dean D.; Hogg, David C. (ed.), From Animals to Robots and Back: Reflections on Hard Problems in the Study of Cognition, A Collection in Honour of Aaron Sloman, Cognitive Systems Monographs, volume. 22, Editora Internacional Springer, pp. 65-73, doi:10.1007/978-3-319-06614-1_5 ^ Tanswell, Fenner (2015), "A problem with the dependence of informal proofs on formal proofs", Philosophia Mathematica, Series III, 23 (3): 295–310, doi:10.1093/philmat/nkv008, MR 3404036 ^ Starikova, Irina; Van Bendegem, Jean Paul (2021), "Revisiting the mutilated chessboard or the many roles of a picture", Logique et Analyse, 64 (255): 289–312, doi:10.2143/LEA.255.0.3290192, MR 4396339 ^ Saltar para: a b McCarthy, John (1999), "Creative Solutions to Problems", AISB Workshop on Artificial Intelligence and Creativity, recuperado 2007-04-27 ^ Saltar para: a b Honsberger, R. (1973), "Gomory's theorem", Mathematical Gems I, Associação Matemática da América, pp. 65–67 ^ Jump up to: a b Mendelsohn, N. S. (2004), "Tiling with dominoes", O Jornal de Matemática da Faculdade, 35 (2): 115-120, doi:10.2307/4146865, JSTOR 4146865. Mendelsohn credits the original publication of Gomory's theorem to Honsberger (1973). ^ Saltar para: a b Propp, Jim (2021), "Conway's influence on the study of random tilings", The Mathematical Intelligencer, 43 (2): 40-46, doi:10.1007/s00283-021-10089-3, MR 4278473 ^ Saltar para: a b Watkins, John J. (2004), De maneira geral: A matemática dos problemas do tabuleiro de xadrez, Imprensa da Universidade de Princeton, pp. 12-14, ISBN 978-0-691-11503-0 ^ Saltar para: a b Wright, Colin (2014), "The mutilated chess board (revisitado)" (PDF), Recreational Mathematics Magazine (1): 4-9, MR 3323392 ^ Thurston, William P. (1990), "Conway's tiling groups", O American Mathematical Monthly, 97 (8): 757–773, doi:10.2307/2324578, JSTOR 2324578, MR 1072815 ^ Urquhart, Alasdair (2003), "Resolution proofs of matching principles", Annals of Mathematics and Artificial Intelligence, 37 (3): 241-250, doi:10.1023/UMA:1021231610627, MR 1969128 ^ Codel, Cayden R.; Reeves, Joseph E.; Heule, Marijn J. H.; Bryant, Randal E. (2021), "Bipartite perfect matching benchmarks" (PDF), in Balyo, Tomáš; Froleyks, Nils; Heule, Marijn; Iser, Markus; Järvisalo, Matti; Suda, Martinho (ed.), Proceedings of SAT Competition 2021: Solver and Benchmark Descriptions, Department of Computer Science Report Series B, volume. B-2021-1, Helsinki: Departamento de Ciência da Computação, University of Helsinki, pp. 52–53, HDL:10138/333647 ^ de Klerk, Etienne; Van Maaren, Hans; Warners, Joost P. (2000), "Relaxations of the satisfiability problem using semidefinite programming", Journal of Automated Reasoning, 24 (1-2): 37–65, doi:10.1023/UMA:1006362203438, MR 1750258 ^ Andrews, Peter B.; Bishop, Mateus (1996), "On sets, types, fixed points, and checkerboards", in Miglioli, Pierangelo; Moscato, Ugo; Mundici, Daniele; Ornaghi, Mario (ed.), Theorem Proving with Analytic Tableaux and Related Methods, 5º Workshop Internacional, TABLEAUX '96, Terrasini, Palermo, Itália, Poderia 15-17, 1996, Processos, Notas de aula em Ciência da Computação, volume. 1071, Springer, pp. 1-15, doi:10.1007/3-540-61208-4_1, 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 ^ Dantchev, Stefan S.; Riis, Søren (2001), "'Planar' tautologies hard for resolution", 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14–17 October 2001, Las Vegas, Nevada, EUA, IEEE Computer Society, pp. 220-229, doi:10.1109/SFCS.2001.959896 ^ 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, MR 2020358 ^ Razborov, Alexander A. (2004), "Resolution lower bounds for perfect matching principles" (PDF), Revista de Ciências da Computação e Sistemas, 69 (1): 3-27, doi:10.1016/j.jcss.2004.01.004, MR 2070797 ^ Korf, Richard E. (1980), "Toward a model of representation changes", Artificial Intelligence, 14 (1): 41-78, doi:10.1016/0004-3702(80)90033-8, MR 0587851 ^ Krishnamurthy, Balakrishnan (1985), "Short proofs for tricky formulas", Acta Informatica, 22 (3): 253–275, doi:10.1007/BF00265682, MR 0806206 ^ Heule, Marijn J. H.; Kiesl, Benjamin; Biere, Armin (2019), "Clausal proofs of mutilated chessboards", in Badger, Julia M.; Rozier, Kristin Yvonne (ed.), NASA Formal Methods - 11th International Symposium, NFM 2019, Houston, TX, EUA, Poderia 7-9, 2019, Processos, Notas de aula em Ciência da Computação, volume. 11460, Springer, pp. 204–210, doi:10.1007/978-3-030-20652-9_13 ^ Paulson, Lawrence C. (2001), "A simple formalization and proof for the mutilated chess board" (PDF), Logic Journal of the IGPL, 9 (3): 475–485, doi:10.1093/jigpal/9.3.475, MR 1828741 ^ Rudnicki, Piotr (1996), The Mutilated Checkerboard Problem in the Lightweight Set Theory of Mizar, Technical Report, volume. TR96-09, University of Alberta Department of Computer Science, doi:10.7939/R3QV3C738 ^ Subramanian, Sakthi (1996), "An interactive solution to the {estilo de exibição n vezes n} mutilated checkerboard problem", Journal of Logic and Computation, 6 (4): 573–598, doi:10.1093/logcom/6.4.573, MR 1406233 ^ Bivens, Irl C.; Holshouser, Arthur L.; Klein, Benjamin G. (Outubro 2008), "Wazir circuits on an obstructed chessboard", Revista Matemática, 81 (4): 276–284, doi:10.1080/0025570X.2008.11953562, JSTOR 27643123 ^ Hanson, Mary Grace; Nash, David A. (Primavera 2018), "Minimal and maximal Numbrix puzzles", Pi Mu Epsilon Journal, 14 (8): 505–514, arXiv:1706.09389 ^ de Bruijn, N. G. (1969), "Filling boxes with bricks", O American Mathematical Monthly, 76 (1): 37-40, doi:10.2307/2316785, JSTOR 2316785, MR 0234841 External links Wikimedia Commons has media related to Mutilated chessboard problem. Gomory's Theorem by Jay Warendorff, The Wolfram Demonstrations Project. Categorias: Tiling puzzlesLogic puzzlesMathematical chess problemsUnsolvable puzzles

Se você quiser conhecer outros artigos semelhantes a **Mutilated chessboard problem** você pode visitar a categoria **Logic puzzles**.

Deixe uma resposta