Parity Arguments

A classic interview puzzle: a chessboard has two opposite corner squares removed, leaving 62 squares. Can you tile the remaining board with 31 dominoes, each covering exactly two adjacent squares? Trying it by hand is a trap — you'll spend twenty minutes shuffling dominoes before either succeeding or giving up, and the puzzle is actually solvable in ten seconds if you stop trying to construct an answer and instead ask what stays invariant no matter how you place the dominoes.

The idea: find a quantity every move preserves (or flips predictably)

A parity argument works by identifying some count — odd or even — that every legal move changes in a fixed, known way (often: it flips every time, or it never changes at all), then comparing the starting count's parity to the target count's parity. If a move always flips a quantity's parity, and you need an even number of moves' worth of flipping to reach the target from the start, but the puzzle demands an odd number (or vice versa), you're done: it's provably impossible, no matter how cleverly you try to construct a solution. No search, no trial and error — just one clean comparison.

Worked example: the mutilated chessboard

Color the chessboard in the standard alternating black-and-white pattern, 32 of each color. Opposite corners are always the same color (both corners of a standard board's long diagonal are the same shade), so removing two opposite corners removes two squares of the same color — say two black squares — leaving 32 white and 30 black, a 62-square board with an uneven color split. Every domino, by construction, covers exactly one adjacent black square and one adjacent white square, no matter where or how it's placed — adjacency on a chessboard always pairs opposite colors. So any tiling using 31 dominoes must cover exactly 31 black and 31 white squares. But the mutilated board only has 30 black squares available — there's no way to cover 31 black squares when only 30 exist. The tiling is impossible, proven without placing a single domino, purely from the fixed black/white pairing every domino is forced to respect.

A second worked example: the light-switch puzzle

100 lightbulbs start off. You make 100 passes: on pass $k$, you flip the switch of every bulb whose number is a multiple of $k$ (pass 1 flips every bulb, pass 2 flips every even-numbered bulb, and so on). Which bulbs end up on? Bulb $n$ gets flipped once for every divisor of $n$ — since each flip toggles on/off, a bulb ends up on exactly when it's been flipped an odd number of times, i.e., when $n$ has an odd number of divisors. Divisors normally pair up ($d$ and $n/d$), which is why most numbers have an even divisor count — except when $n$ is a perfect square, where one divisor pairs with itself ($\sqrt{n} \times \sqrt{n}$) and breaks the pairing, leaving an odd count. So the bulbs left on are exactly the perfect squares: 1, 4, 9, 16, ..., 100 — ten bulbs, found without simulating a single pass, purely by tracking the parity of each bulb's divisor count.

What this means in practice

Parity and invariant arguments are the fastest tool for "prove this is impossible" questions, which show up constantly in technical interviews precisely because they separate candidates who search blindly from those who look for a preserved quantity first. The same technique generalizes past strict odd/even counting to any conserved quantity under a set of moves — mod-3 colorings, weighted sums, or any invariant that a legal move can't change past a fixed rule — but parity (mod 2) is the simplest and most common version to reach for first.