Jump to: navigation, search

Checkerboard and dominoes

523 bytes added, 17:00, 14 July 2013
no edit summary
A regular checker board has 64 squares (arranged in an 8 by 8 square). You happen to have a set of dominoes, each of which can cover exactly 2 squares on the checker board. Suppose you cut out one square from opposite corners. Is it possible to cover this mutilated board with non-overlapping dominoes? That is, is there a way to pair up the remaining 62 squares so that the two squares in each pair are adjacent? Prove your answer.
{{Hint | Checkerboards have squares of two different colors.}}
{{Answer | No.}}
{{Solution | The two squares at opposite corners are either both white or both black. In either case, the remaining 62 squares will consist of 30 squares of one color, and 32 squares of the other. No matter how a domino is placed on the board, it will cover exactly one square of each color. Thus it is impossible to cover every remaining square.}}
==See also==
[[Checkerboard cut-up]]
[[Longest road]]
[[Category: Combinatorics]]
[[Category: Parity]]
CheckUser, Bureaucrats, checkuser, developer, Administrators

Navigation menu