Tuesday, March 25, 2014

Covering a chess board with dominos

Problem:

There is an 8×8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible)

Solution:


No, it's not possible. Two diagonally opposite squares on a chess board are of the same color. Therefore, when these are removed, the number of squares of one color exceeds by 2 the number of squares of another color. However, every piece of domino covers exactly two squares and these are of different colors. Every placement of domino pieces establishes a 1-1 correspondence between the set of white squares and the set of black squares. If the two sets have different number of elements, then, by the Pigeonhole Principle, no 1-1 correspondence between the two sets is possible.(Pigeon hole principle - If m pigeons are put into m pigeonholes, there is an empty hole iff there's a hole with more than one pigeon. Formally speaking, let |A| denote the number of elements in a finite set A. For two finite sets A and B, there exists a 1-1 correspondence f: A->B iff |A| = |B|. )

Because the question says ‘single domino can cover exactly two squares’ but it does not specify how these two squares are aligned. If the two squares have to be horizontally or vertically next to each other, then it’s impossible to do this (explanation later). If a domino can be put on two diagonal connected squares, then it’s always possible. Think about a simplified version: a 4*4 board. You can put the dominos pizza in this way:
–|*
–||
–\|
*–\
Where ‘*’ represented the corners been cut off. ‘–’ represents a horizontally put domino, two vertically aligned ‘|’ represents a vertical domino and two ‘\’ represents a diagonal domino.
Next, we explain if the domino can only be put horizontally or vertically, there is no possible solution. A 8*8 chess board contains 32 white and 32 black squares. If two corners are removed, without loss of generality, let us assume the board leaves with 30 white and 32 black squares. A single domino, put horizontally or vertically, will occupy 1 white and 1 black square. Hence, 31 dominos will cover exactly 31 white and 31 black squares. But we have 30 white and 32 black squares. Therefore it’s impossible to cover the board with 31 dominos.

References :

                    tian runhecut-the-knot.org,

0 comments:

Post a Comment