x. Parity, Coloring and Mod Observations

The quickest impossibility proofs: find a quantity that the operation preserves modulo something, and compare the start and the target.

Invariant	Typical operation
parity of the sum	change two elements by $\pm 1$ each, or add to a pair
sum modulo $k$	operations that add a multiple of $k$ in total
xor of all elements	replace $a,b$ by $a\oplus b$ and $0$, or by $a\oplus x,b\oplus x$
gcd of all elements	replace $a$ by $a-b$ (Euclid steps)
permutation parity	swapping two elements flips it; a 3-cycle keeps it
chessboard colour count	dominoes cover one black and one white cell
colouring mod $k$	$1\times k$ tiles cover each colour class $x+y\mathrm{mod}k$ once
alternating sum	add 1 to two adjacent elements

The sliding puzzle (15-puzzle)

An $R\times C$ board with tiles $\mathrm{1..}RC-1$ and a blank; slide a tile into the blank. The goal is $1,2,\dots ,RC-1$ in row-major order with the blank last.

bool slidingSolvable(int R, int C, const vector<int>& g) {
    vector<int> t; int blankRow = 0;
    for (int i = 0; i < R * C; i++) if (g[i]) t.push_back(g[i]); else blankRow = i / C;
    int inv = 0;                                            // O(n^2) is fine; use a BIT for big boards
    for (int i = 0; i < sz(t); i++) for (int j = i + 1; j < sz(t); j++) inv += t[i] > t[j];
    if (C % 2 == 1) return inv % 2 == 0;
    return (inv + blankRow) % 2 == (R - 1) % 2;
}

Proof: solvable iff the parity condition holds

Read the tiles in row-major order, skipping the blank. A horizontal move does not change this sequence. A vertical move takes one tile and moves it past exactly $C-1$ others in the sequence, changing the inversion count by $C-1$ steps of $\pm 1$, and changes the blank’s row by one. If $C$ is odd, $C-1$ is even, so the inversion parity is invariant; the goal has $0$ inversions. If $C$ is even, every vertical move flips the inversion parity and the blank-row parity together, so $\text{inv}+\text{blankRow}$ is invariant mod 2; the goal has blank row $R-1$. This proves necessity. Sufficiency (every configuration satisfying the condition is reachable, for $R,C\ge 2$) is the classical theorem: 3-cycles of tiles can be performed by rotating the blank around a $2\times 2$ block, and 3-cycles generate all even permutations. Verified by BFS for boards $2\times 2$, $2\times 3$, $3\times 2$, $2\times 4$, $3\times 3$.

Mutilated chessboard and friends

• An $8\times 8$ board with two opposite corners removed cannot be tiled by dominoes: both removed cells have the same colour, and each domino covers one of each.
• A $10\times 10$ board cannot be tiled by $1\times 4$ tiles: colour cell $(x,y)$ by $(x+y)\mathrm{mod}4$; each tile covers each colour once, but the colour counts are $25,26,25,24$.
• Replacing $a,b$ by $|a-b|$ preserves the parity of the sum, so the parity of the final number is fixed.

Proof: colouring arguments

A tile placed anywhere covers cells whose colours are $c,c+1,\dots ,c+k-1(\mathrm{mod}k)$, which is one cell of each colour class. A tiling therefore uses each colour class equally often, so if the class sizes differ, no tiling exists. For the $10\times 10$ board, the number of cells with $(x+y)\equiv c(\mathrm{mod}4)$ is $25,26,25,24$ for $c=0,1,2,3$.

Related: Invariants and Extremal Arguments, Counting Fundamentals (permutation parity).