Problem 3 - A Gentle Introduction to the Art of Mathematics

Question

Provide an argument as to why an \(8 \times 8\) chessboard with two squares pruned from diagonally opposite corners cannot be tiled with dominoes.

Step-by-Step Solution

Answer

It is impossible because the removed squares disrupt the balance of black and white squares needed for dominos to tile the board evenly.

Step 1 - Understand the Problem

An 8x8 chessboard has 64 squares. A domino covers exactly 2 squares, so a complete tiling would require 32 dominoes. Two squares are removed, so only 62 squares remain to be covered.

Step 2 - Color the Chessboard

Color the chessboard in a checkerboard pattern where alternating squares are black and white. Quite similar to the standard chessboard, an 8x8 board has 32 white squares and 32 black squares if all squares are present.

Step 3 - Identify the Removed Squares

Diagonally opposite corners mean that one white square and one black square are removed. Therefore, the remaining 62 squares consist of 31 white squares and 31 black squares.

Step 4 - Describe Domino Tiling

Each domino placed on the chessboard will always cover one white square and one black square, maintaining the balance between black and white squares being covered.

Step 5 - Argue the Impossibility

With 31 white squares and 31 black squares, it is impossible to tile the board completely because a domino would always cover an equal number of white and black squares (1 white and 1 black). Therefore, 62 squares cannot be covered with 31 dominoes when the colors are imbalanced.

Key Concepts

checkerboard pattern

A checkerboard pattern is a visual layout that alternates between two colors, usually black and white. Imagine a standard chessboard where every square is either black or white. This pattern is useful in mathematical tiling problems because it helps visualize how tiles will fit.

For an 8x8 board, which has 64 squares, there are 32 black squares and 32 white squares. When two squares are removed, particularly diagonally opposite corners, these are a black and a white square. This affects the balance of the pattern significantly. Using this checkerboard approach allows us to see imbalances or challenges in tiling quickly.

domino tiling

Domino tiling involves covering a surface without gaps or overlaps using dominos. Each domino covers exactly 2 squares. In an 8x8 chessboard, tiling with dominos would mean placing 32 dominos to cover all 64 squares.

When tiling with dominos on a checkerboard, each domino must cover one black and one white square. This ensures that each color is covered equally. If two opposite corners (one black and one white) are removed, balancing the tiling becomes tricky as that creates 31 black and 31 white squares.

proof by contradiction

Proof by contradiction is a logical method where you assume the opposite of what you're trying to prove is true, and then show that this assumption leads to a contradiction.

For this 8x8 chessboard problem, one might assume it is possible to tile the board with the two removed (diagonally opposite) squares. You would then show that this assumption leads to an inconsistency.

The contradiction here is in the balance of black and white squares. Since each domino must cover one black and one white square, having an equal number of each color is necessary. Removing two opposite corners disrupts this balance (31 black and 31 white), proving tiling under these conditions is impossible.

chessboard problem

The chessboard problem refers to a classic tiling puzzle involving a standard 8x8 chessboard. The challenge is whether it's possible to cover the board using dominos when certain conditions are applied, such as pruned squares.

Here, removing two diagonally opposite corners means taking out two squares of different colors. Since each domino covers one black and one white square, if the number of black and white squares is not equal, it's impossible to complete the tiling. In this scenario, with 31 black and 31 white squares left, the imbalance makes it clear that the chessboard cannot be fully tiled.