The Mutilated Chessboard: Part I

Lafayette Park Chess Tables
Here is a little puzzle, just for fun. I may post hints in the comments if people ask.

Take an 8×8 chessboard.

Chess Board

Imagine we have a set of dominoes and we want to cover this chessboard. Each domino covers up exactly two squares. The goal is to cover the chessboard completely, in a way that none of the dominoes overlap or stick off the board.

First question: is that possible?

Answer: It is. Here is one way to do it. Each of the colorful rectangles below represents a domino.

Dominoes tiling 8x8

A setup like the one in the picture above, where the board is completely covered with dominoes that don’t overlap and don’t go off the board, is called a tiling.

Now take an 8×8 board and cut off the top right corner and the bottom left corner.

Mutilated checkerboard 3

Here comes the puzzle.

Can this board, without the two boxes on the corners, be covered completely with dominoes? Is there a tiling of this board?

There are two possible types of solutions to this puzzle. The format of the solution depends on whether a tiling exists or not.

  1. There might be a tiling that works. In that case, a solution would be the tiling: a picture of how to cover the board.
  2. There might be no tiling that works. In other words, it might be impossible to cover this board with dominoes, no matter how many combinations you try. In that case, a solution would consist of a reason why no tiling can work. If there can’t be a tiling, then why not? Can you prove it?

This is called the “Mutilated Chessboard” problem. It doesn’t involve a lot of mathematical sophistication. It does require creative problem solving. My favorite solution to this puzzle is clever, but simple.

Feel free to post thoughts or questions in the comments! I’ll try to respond, and maybe even post hints.

And no full solutions, please. We’ll get to that in the next post.

Advertisements

4 thoughts on “The Mutilated Chessboard: Part I

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