Cover a chess board with dominos

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)

My initial thoughts (Solutions):
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 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: