Invariants: Proving Impossibility in Grid Problems

What is an Invariant?

At its core, an invariant is a property or quantity that does not change while a system undergoes a series of transformations. If we can find an invariant, we can use it as a powerful logical tool. If the initial state of a system has a certain value for an invariant, and a target state has a different value, then it is impossible to reach the target state from the initial one.

Let's begin by formalizing this idea.

The Classic Example: Coloring a Chessboard

The most intuitive way to understand invariants is through coloring. Let's explore the famous "mutilated chessboard" problem. A standard 8x8 chessboard has two opposite corners removed. Can this new 62-square board be perfectly tiled with 31 dominoes of size 2x1?

To see this problem explained visually and understand the solution, watch the following video.

As the video demonstrates, the invariant is the difference between the number of uncovered black squares and uncovered white squares.

• Initial State (mutilated board): An 8x8 board has 32 black and 32 white squares. The opposite corners are the same color (let's say black). Removing them leaves 30 black squares and 32 white squares. The difference is 2.
• The Operation: Placing a 2x1 domino always covers exactly one black and one white square.
• The Invariant: Each move reduces the count of black squares by one and white squares by one. Therefore, the difference between the number of available black and white squares remains constant throughout the tiling process. It will always be 2.
• Target State (fully tiled board): We want 0 uncovered black squares and 0 uncovered white squares. In this state, the difference is 0.

Since the invariant has a value of 2 in the initial state and must remain 2, it can never reach the target state's value of 0. Therefore, the tiling is impossible. This is the fundamental logic of an invariant proof.

Beyond Simple Coloring: Parity and Modular Arithmetic

The coloring argument is really a statement about parity. A domino covers an equal number of squares of each color. Let's generalize this to invariants based on numbers. Your background in number theory, especially with parity and remainders (modular arithmetic), will be very useful here.

Consider this problem from a past International Mathematical Olympiad Shortlist (ISL).

In this problem, the operation is adding k to two adjacent squares. Since adjacent squares on a chessboard always have different colors, one is black and one is white. The sum of numbers on black squares, Sb, increases by k, and the sum on white squares, Sw, also increases by k. The difference, Sb - Sw, remains unchanged. This is the invariant. For all numbers to become zero, we need Sb = 0 and Sw = 0, which implies Sb - Sw = 0. By the principle of invariants, this must also be true of the initial state.

Let's look at another example where the invariant is not just parity (mod 2) but a value in mod 5.

Here, the quantity (x + y) mod 5 is not strictly invariant, but it changes in a very predictable way: it either stays the same or is multiplied by 3.

• Start: (0, 1) -> x + y = 1. Mod 5, the sum is 1.
• Possible values for (x+y) mod 5 after any number of moves can only be 1, 3, (3*3=9)≡4, (4*3=12)≡2, (2*3=6)≡1, .... The set of reachable values for (x+y) mod 5 is {1, 2, 3, 4}.
• Target: (0, 0) -> x + y = 0. Mod 5, the sum is 0.

Since 0 is not in the set of reachable values, we can never get to the origin.

The 15-Puzzle: A More Complex Invariant

Now, let's tackle a famous and more difficult problem: the 15-puzzle. The puzzle consists of 15 numbered tiles in a 4x4 grid with one empty space. A move consists of sliding a tile adjacent to the empty space into it. The goal is to get the tiles into numerical order.

In the 1880s, the puzzle master Sam Loyd offered a $1,000 prize for solving the puzzle from the configuration shown below, known as "Loyd's challenge".

This challenge is impossible. To prove it, we need to construct a more sophisticated invariant. The state of the puzzle is determined not just by one number, but by a combination of two properties:

1. The parity of the tile permutation: A permutation is a reordering of the tiles. We can measure it by the number of "transpositions" (swaps of two tiles) needed to get from the solved state to the current one. An even number of swaps is an even permutation; an odd number is an odd permutation.
2. The position of the blank space: We can track the row number of the blank space (counting from the top, 1 to 4).

Let's observe what happens to these two properties with every single move.

A single move of a tile is equivalent to swapping that tile with the blank space.

• If we slide a tile horizontally, the blank space stays in the same row. The tile permutation changes by one swap. So, the permutation parity flips (odd ↔ even), but the blank's row parity stays the same.
• If we slide a tile vertically, the blank space moves up or down by one row. This flips the parity of the blank's row number (odd ↔ even). It also changes the tile permutation by one swap, flipping its parity.

This seems complicated. However, let's define an invariant function L for the puzzle state:
$L=(\text{number of inversions})+(\text{row of blank space})$
An "inversion" is a pair of tiles that are in the wrong order relative to each other. The parity of the number of inversions is the same as the parity of the permutation. So, let's simplify and just use perm_parity.
$K=(\text{perm\_parity})+(\text{row\_of\_blank})$
Let's look at K mod 2.

• Horizontal move: perm_parity flips (changes by 1 mod 2). row_of_blank is unchanged. The total change in K is 1 (mod 2).
• Vertical move: perm_parity flips (changes by 1 mod 2). row_of_blank changes by 1, so its parity flips (changes by 1 mod 2). The total change in K is 1 + 1 = 2 ≡ 0 (mod 2).

This doesn't seem to give us a simple invariant. Let's reconsider. The key insight, which is subtle, is that any move can be thought of as the blank space moving. Each move of the blank is a transposition with an adjacent tile. The total number of transpositions to reach a state is what matters for the permutation. A horizontal move of the blank is one transposition. A vertical move is also one transposition.

A better invariant is (parity of permutation) + (parity of Manhattan distance of blank from corner). Let's use a simpler version that works for the 4x4 case. Let's define the invariant S as:
$S=(\text{Parity of the permutation})+(\text{Row number of the blank space, counting from 1})$
The key is that any move changes the number of transpositions by 1, so it flips the permutation parity. At the same time, any move changes the Manhattan distance of the blank from the bottom-right corner by ±1. Let's check row number specifically.
A horizontal move changes the permutation parity but not the row number. A vertical move changes both. This is not an invariant.

Let's try again, carefully. The actual invariant is (parity of permutation) + (parity of the row index of the blank tile). For any legal move (a single slide), the value of ((number of inversions) + (row of blank)) mod 2 is invariant.

Let's analyze Loyd's puzzle with this invariant I = (number of inversions) + (row of blank):

• Solved State:

  • The permutation is the identity. Number of inversions is 0 (even).
  • The blank is in row 4.
  • I_solved} = 0 + 4 = 4 (even).

• Loyd's Challenge State:

  • The only tiles out of order are 14 and 15. This is a single swap from the solved state. A single transposition changes the number of inversions by an odd number. So, the number of inversions is odd.
  • The blank is in row 4.
  • `I_loyd = (\text{odd}) + 4 = \text{odd}$.

Since I_solved is even and I_loyd is odd, and I mod 2 is an invariant, it is impossible to get from the solved state to Loyd's challenge state. He was never in danger of paying the prize!

Practice Problems

Now it's your turn to apply these concepts. As you requested, here are a few problems to practice your skills. For each one, the key is to find the right invariant.

1. (Warm-up) The cells of a 7×7 board are colored like a chessboard, with the corners being black. You are allowed to repaint any two adjacent cells (sharing a side) to their opposite colors. Is it possible to make the entire board white? (Hint: How many black and white squares are there initially? What does one operation do to the count of black squares?)

2. (Grid and Coordinates) On a 15×15 board, 15 rooks are placed so that no two rooks attack each other (i.e., one rook per row and column). Then, each rook makes a single move like a knight. Prove that after this, at least two rooks must be attacking each other. (Hint: Assign coordinates (x, y) to each square. What is the sum of all coordinates of the rooks initially? How does a knight's move change the sum of a piece's coordinates?)

3. (Number Line) Three coins are on integer points on the number line. A move consists of choosing two coins, moving one 1 unit to the right and the other 1 unit to the left. What initial condition on the coin positions is necessary and sufficient to be able to move all coins to a single point? (From Swiss Olympiad, 2010).

Conclusion

In this lesson, you've learned to wield the powerful technique of invariants to prove impossibility. We saw that an invariant can be a simple property like the color of a square, the parity of a count, a sum modulo n, or a more complex function like the one used to solve the 15-puzzle. The underlying logic is always the same: if an operation preserves a certain property, then no sequence of those operations can lead to a state where that property is different.

This is a fundamental skill for Olympiad-level combinatorics. As you continue, always ask yourself when faced with a process: "What stays the same?"

In our next lesson, we will explore a related concept called monovariants. These are quantities that are not strictly constant but change in only one direction—either always increasing or always decreasing. This property is equally powerful, especially for proving that a process must eventually stop.