Invariant Arguments

An invariant is a quantity that does not change under the allowed operations of a problem. If the initial and target states have different invariant values, the transformation is impossible. The strategy: 1. Identify a candidate invariant (parity, a sum, a modular residue, a coloring) 2. Prove it is preserved by every allowed move 3. Check whether the initial and target states agree on the invariant Concrete example: You have a row of 100 coins, all heads up. Each move flips exactly 3 adjacent coins. Can you make them all tails? Observe that each move changes the number of heads by $+3, +1, -1,$ or $-3$ — all odd changes. The number of heads starts at 100 (even). After any number of moves, the parity of the head count remains even. But 0 heads is also even, so parity alone does not settle it. Instead, consider the count modulo 3: it starts at $100 \equiv 1 \pmod{3}$, and each move changes it by $\pm 3 \equiv 0 \pmod{3}$. The target 0 $\equiv 0 \pmod{3}$. Since $1 \not\equiv 0$, it is impossible. Common invariants: - Parity (even/odd count) — the most common - Sum modulo $k$ — especially mod 2 or mod 3 - Coloring arguments — assign colors to positions and track color sums - Monovariants — quantities that only increase (or decrease), eventually forcing termination When to use: Problems that ask "is this transformation possible?" or "prove this process terminates." If you suspect impossibility, hunt for an invariant. If you need termination, look for a monovariant — a quantity that strictly changes in one direction with each step.