Mutilated chessboard problem

Mutilated chessboard problem
Solid white.svg a b c d e f g h Solid white.svg
8  black king  black king  black king  black king  black king  black king  black king  cross 8
7  black king  black king  black king  black king  black king  black king  black king  black king 7
6  black king  black king  black king  black king  black king  black king  black king  black king 6
5  black king  black king  black king  black king  black king  black king  black king  black king 5
4  black king  black king  black king  black king  black king  black king  black king  black king 4
3  black king  black king  black king  black king  black king  black king  black king  black king 3
2  black king  black king  black king  black king  black king  black king  black king  black king 2
1  cross  black king  black king  black king  black king  black king  black king  black king 1
Solid white.svg a b c d e f g h Solid white.svg
Mutilated chessboard problem.

The mutilated chessboard problem is a tiling puzzle introduced by Gamow & Stern (1958) and discussed by Martin Gardner in his Scientific American column "Mathematical Games." The problem is as follows:

Suppose a standard 8x8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2x1 so as to cover all of these squares?

Most considerations of this problem in literature provide solutions "in the conceptual sense" without proofs.[1] John McCarthy proposed it[2] as a hard problem for automated proof systems.[3] In fact, its solution using the resolution system of inference is exponentially hard.[4]

Contents

Solution

The puzzle is impossible to complete. A domino placed on the chessboard will always cover one white square and one black square. Therefore a collection of dominoes placed on the board will cover equal numbers squares of each colour. 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, then 32 black squares and 30 white square remain, so it is again impossible. [5]

A mutilated chessboard problem example.
Mutilated chessboard example showing like coloured empty squares

Gomory's theorem

The same impossibility proof shows that no domino tiling exists whenever any two white squares are removed from the chessboard. However, if two squares of opposite colors are removed, then it is always possible to tile the remaining board with dominos; this result is called Gomory's theorem,[6] and is named after mathematician Ralph E. Gomory, whose proof was published in 1973.[7] Gomory's theorem can be proven using a Hamiltonian cycle of the grid graph formed by the chessboard squares; the removal of two oppositely-colored squares splits this cycle into two paths with an even number of squares each, both of which are easy to partition into dominos.

Notes

  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, "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 (1995), "The Mutilated Chessboard Problem—checked by Mizar", in Boyer, Robert; Trybulec, Andrzej, QED Workshop, II, Warsaw University, pp. 25–26, http://citeseer.ist.psu.edu/87819.html, "The problem presented by John McCarthy during his lecture "Heavy duty set theory"1 has been resolved here." 
  3. ^ Arthan, R. D. (2005) (PDF), The Mutilated Chessboard Theorem in Z, http://www.lemma-one.com/ProofPower/examples/wrk071.pdf, retrieved 2007-05-06, "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 (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, retrieved 2007-04-27 
  6. ^ Watkins, John J. (2004), Across the board: the mathematics of chessboard problems, Princeton University Press, pp. 12–14, ISBN 9780691115030 .
  7. ^ According to Mendelsohn, the original publication is in Honsberger's book. Mendelsohn, N. S. (2004), "Tiling with dominoes", The College Mathematics Journal (Mathematical Association of America) 35 (2): 115–120, doi:10.2307/4146865, JSTOR 4146865 ; Honsberger, R. (1973), Mathematical Gems I, Mathematical Association of America .

References

  • Gamow, George; Stern, Marvin (1958), Puzzle-Math, Viking Press, ISBN 978-0-333-08637-7 
  • Gardner, Martin (1994), My Best Mathematical and Logic Puzzles, Dover, ISBN 0486281523 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Mathematical puzzle — Mathematical puzzles make up an integral part of recreational mathematics. They have specific rules as do multiplayer games, but they do not usually involve competition between two or more players. Instead, to solve such a puzzle, the solver must …   Wikipedia

  • Домино — Игра в Домино У этого термина существуют и другие значения, см. Домино (значения). Домино  игра, в процессе которой выстраивается цепь костяшек («костей», «камней»), соприкасающихся половинками с одинаковым числом очко …   Википедия

  • Шахматная доска — с расставленными фигурами перед началом игры Шахматная доска  игровое поле в шахматах, шашках …   Википедия

  • Chess puzzle — A chess puzzle is a puzzle in which knowledge of the pieces and rules of chess is used to solve logically a chess related problem. The longstanding popularity of chess has paved the way for a rich tradition of such chess related puzzles and… …   Wikipedia

  • Domino (mathematics) — The single free domino In mathematics, a domino is a polyomino of order 2, that is, a polygon in the plane made of two equal sized squares connected edge to edge.[1] When rotations and reflections are not considered to be distinct shapes, there… …   Wikipedia

  • Domino tiling — of a square A domino tiling of a region in the Euclidean plane is a tessellation of the region by dominos, shapes formed by the union of two unit squares meeting edge to edge. Equivalently, it is a matching in the grid graph formed by placing a… …   Wikipedia

  • Tiling puzzle — Tiling puzzles are puzzles involving two dimensional packing problems in which a number of flat shapes have to be assembled into a larger given shape without overlaps (and often without gaps). Some tiling puzzles ask you to dissect a given shape… …   Wikipedia

  • List of impossible puzzles — This is a list of puzzles which have been proven impossible. An impossible puzzle is a puzzle that cannot be solved by following the directions or criteria for that puzzle.* Mutilated chessboard problem * Some variations of Fifteen puzzle * List… …   Wikipedia

  • Parity (mathematics) — In mathematics, the parity of an object states whether it is even or odd. This concept begins with integers. An even number is an integer that is evenly divisible by 2, i.e., divisible by 2 without remainder; an odd number is an integer that is… …   Wikipedia

  • Geostrategy — The North Atlantic Treaty Organisation is a geostrategic military alliance concerned with most of Europe and North America Geostrategy, a subfield of geopolitics, is a type of foreign policy guided principally by geographical factors as they… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”