Parity Arguments

A parity argument is the special case of invariant reasoning where the invariant is the oddness or evenness of some quantity. It is the single most common technique for impossibility proofs in discrete mathematics. Concrete example: Can you tile a standard 8$\times$8 chessboard with two opposite corners removed using 2$\times$1 dominoes? Each domino covers exactly one black and one white square. The full board has 32 black and 32 white squares. Removing two opposite corners removes 2 squares of the same color, leaving 30 of one color and 32 of the other. Since each domino covers one of each, a perfect tiling requires equal counts. Impossible. Common parity patterns: - Transposition parity: Every permutation is either even or odd (even or odd number of transpositions). A sequence of swaps cannot change parity. - Checkerboard coloring: Assign black/white to grid cells; moves that preserve the color balance have parity constraints. - Sum parity: If every operation changes a sum by an even amount, the sum's parity is fixed. Key formula for permutations: The sign of a permutation $\sigma$ is $\text{sgn}(\sigma) = (-1)^{\text{number of inversions}}$. Swapping two elements flips the sign. When to use: Whenever a problem involves tiling, swapping, or discrete operations and asks "is it possible?" — try tracking parity first. It is the simplest invariant to check and resolves a surprising number of problems. If parity does not suffice, escalate to mod 3 or other invariants.