Checkerboard Patterns in Grid Puzzles

The Classic: A Mutilated Chessboard

Let's begin with one of the most famous problems in this field.

An 8x8 chessboard has two diagonally opposite corners removed. Can the remaining 62 squares be tiled perfectly with 31 dominoes, where each domino covers exactly two adjacent squares?

At first glance, this seems possible. The area matches: 62 squares to be covered by 31 dominoes of area 2. However, trying to tile it soon becomes frustrating. This is where coloring provides a beautiful and definitive proof of impossibility.

A standard chessboard is already colored with a checkerboard pattern. This is our key insight. The following short videos explain the solution clearly.

The argument rests on a simple but crucial invariant:

1. The Tile Invariant: Every 1x2 domino, no matter where it is placed on a checkerboard (horizontally or vertically), must cover exactly one white square and one black square.
2. The Board Analysis: A standard 8x8 chessboard has 32 white squares and 32 black squares. The two diagonally opposite corners are always the same color. Let's say they are both white.
3. The Contradiction: When we remove two white squares, the mutilated board has 32 black squares but only 30 white squares. To tile this board with 31 dominoes, we would need to cover 31 black squares and 31 white squares, according to our tile invariant. Since the board doesn't have 31 white squares, the tiling is impossible.

This coloring argument transforms a difficult spatial puzzle into a simple counting problem. This is a recurring theme in combinatorics.

To solidify this, let's look at the same argument presented slightly differently.

Applying Coloring to Movement Puzzles: The Knight's Tour

This principle extends beyond tiling. You mentioned an interest in the Knight's Tour, and coloring is the perfect tool to analyze it.

Is it possible for a knight to start on a 5x5 chessboard, visit every square exactly once, and return to its starting square (a "closed tour")?

Let's analyze the knight's move on a checkerboard.

This observation is our invariant. A knight's tour is a path of moves, so the colors of the squares visited must alternate: Black, White, Black, White, ...

1. The Board Analysis: A 5x5 board has 25 squares in total. If we color it like a checkerboard, it will have an unequal number of black and white squares. For example, it might have 13 black squares and 12 white squares.
2. The Path Analysis: A closed tour on a 25-square board is a sequence of 25 distinct squares $s_1,s_2,\dots ,s_{25}$ and a final jump from $s_{25}$ back to $s_1$. The colors of the squares in the sequence must alternate. For a path to visit all 25 squares, it must visit 13 of one color and 12 of the other. For instance, the sequence of colors could be B, W, B, W, ..., B.
3. The Contradiction: In such a sequence, the starting square $s_1$ and the ending square $s_{25}$ must both be black. However, for the tour to be closed, the knight must be able to jump from $s_{25}$ to $s_1$. Since a knight can only jump between squares of different colors, it cannot jump from a black square ($s_{25}$) to another black square ($s_1$). Therefore, a closed knight's tour on a 5x5 board is impossible.

This reasoning applies to any board with an odd number of squares. The requirement of an alternating color path means a closed tour can only exist on a board with an even number of squares, which in turn implies there must be an equal number of black and white squares.

Coloring on the Coordinate Plane

The power of coloring isn't limited to physical boards. It can be applied to abstract geometric problems on the coordinate plane, aligning with your interest in combinatorial geometry.

Let's break down this elegant proof:

1. The Coloring: The lattice points $(x,y)$ are colored based on the parity of the sum of their coordinates. A point is "white" if $x+y$ is even and "black" if $x+y$ is odd. This is just a standard checkerboard pattern.
2. The Distance Invariant: For a line segment between two lattice points $(x_1,y_1)$ and $(x_2,y_2)$ with an integer length $L$, we have $L^2=(x_2-x_1{)}^2+(y_2-y_1{)}^2$. Taking this modulo 2, we get $L\equiv (x_2-x_1)+(y_2-y_1)(\mathrm{mod}2)$, which rearranges to $L\equiv (x_2+y_2)-(x_1+y_1)(\mathrm{mod}2)$.
3. The Consequence: This means the parity of the distance $L$ is the same as the parity of the difference of the "color values" ($x+y$).
   • If two points have the same color, the integer distance between them must be even.
   • If they have different colors, the integer distance must be odd.
4. The Proof: The perimeter of a pentagon with vertices $V_1,\dots ,V_5$ is the sum of the side lengths $L_{12}+L_{23}+L_{34}+L_{45}+L_{51}$. The parity of the perimeter is a telescoping sum: $$(\text{color}(V_2)-\text{color}(V_1))+(\text{color}(V_3)-\text{color}(V_2))+\cdots +(\text{color}(V_1)-\text{color}(V_5))\equiv 0(\mathrm{mod}2)$$ Therefore, the perimeter must be an even integer.

Practice Problems

Now it's your turn to apply these coloring arguments. For each problem, identify the board, the tiles (or moves), and the invariant you can establish with a 2-coloring.

1. (Tetromino Tiling) An L-shaped tetromino is a 2x2 square with one cell removed. Prove that a 4x11 rectangle cannot be tiled by L-shaped tetrominoes. (Hint: Color the 4x11 board like a checkerboard. How many black and white squares are there? Then, analyze the colors covered by a single L-tetromino.)

2. (Domino Tiling on a Modified Board) An 8x8 chessboard has all four of its corner squares removed. Can the remaining 60 squares be tiled by 1x2 dominoes? Justify your answer using a coloring argument.

3. (Another Knight's Tour Problem) Is there a closed knight’s tour on a 4x4 chessboard? What about a 3x3 board? Use the coloring principle to prove your answers.

Conclusion

In this lesson, you've learned to wield one of the most fundamental tools in combinatorial problem-solving: 2-coloring. We've seen that by imposing a simple checkerboard pattern, we can reveal a hidden structure—an invariant—that makes proving impossibility straightforward. The key takeaway is to analyze how both the board and the pieces (or moves) interact with the coloring. An imbalance in colors often leads to a swift contradiction.

We started with the classic mutilated chessboard, extended the principle to a movement puzzle you're interested in (the Knight's Tour), and even applied it to a problem in combinatorial geometry. This technique of finding an invariant through coloring is a cornerstone of Olympiad-level problem-solving.

In our next lesson, we will build directly on this foundation. What happens when a simple 2-coloring isn't enough? We will explore how to use more than two colors, or colors based on modular arithmetic, to crack even more complex grid-based puzzles.