Checkerboard and dominoes: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
Oscarlevin (talk | contribs) No edit summary |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[File:Checkerboard_dominoes.png|right|150px]] | |||
This is a rather well known puzzle, but for good reason. | |||
==Puzzle== | ==Puzzle== | ||
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. | 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. | ||
==Help== | |||
{{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: Combinatorics]] | ||
[[Category: Parity]] | |||
Current revision as of 16:08, 14 July 2013
This is a rather well known puzzle, but for good reason.
Puzzle
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.
Help
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.