Search 72,251 tutors
FIND TUTORS

Think Tank Puzzle 5

The Mutilated Chessboard

A chessboard has 64 squares, 8 by 8. If you have 32 dominoes, each the size of 2 side-by-side chessboard squares, you’ll be able to exactly cover the chessboard with the dominoes. (In fact, there are very many ways you could arrange the dominoes to cover the 64 squares of the board!)

But suppose you cut off any two diagonally opposite corner squares of the chessboard, leaving 62 squares. What patterns of 31 dominoes will exactly cover the mutilated chessboard?

This is another good exercise in creative problem-solving. Try to observe your own thought processes as you try to solve this. Are you methodical or do you make random guesses? Do you visualize solving the problem or analyze it differently? Do you attack the whole problem head-on, or try to solve a similar but smaller and simpler problem first?

Comments

Here is a hint about this problem... Think about how you would cover the chessboard with dominoes. You could place all of the dominoes horizontally or vertically, 4 per row, or you could place some horizontally and some vertically. But notice what happens when you mix the 2 directions of placement. No matter how many horizontal dominoes cover part of a row, you will have to have an EVEN number of vertically placed dominoes in that row. This problem is very much about PARITY--evenness or oddness. Does that help you understand how to cover the chessboard if it is missing 2 diagonal corners?
For those of you who have been struggling with this, here's the answer... There is no way to cover the mutilated chessboard with dominoes. Notice that although the squares of a chessboard alternate in color, the diagonal corners are the same color. So, if diagonal corners are removed, there are more squares remaining of one color than there are of the other color. BUT, each domino covers two squares--one of each color. So no matter how you arrange the dominoes, you will always cover the same number of squares of each color. Therefore, it is impossible to cover the mutilated board with dominoes. This is an example of a non-existence proof. Rather than try to examine every possible covering, which would take LOTS of work, we can quickly show (by a parity analysis) that no covering can ever exist.

Seattle tutors