← All Strategies
◈
Strategy 06 of 12Invariants
Find what remains constant when everything changes
ProcessesImpossibleParity
An invariant is a quantity that doesn't change while something else does. If the start and end states have different invariant values, the transformation is impossible. Invariants can be numerical, modular, or structural.
When to use it
- →When you have a process or game
- →When asked 'can you get from state A to state B?'
- →When there is repetition of an operation
- →When you want to prove something is impossible
How to think (step by step)
- 1Understand the process: What exactly changes?
- 2Search for an invariant: What might remain constant?
- 3Verify: Does it remain constant at each step?
- 4Apply: If start ≠ end value of invariant, it's impossible
Practice Problems
Three problems at increasing difficulty — try each before revealing the hint or solution.
📘Basic
Write \(1, 2, 3, \ldots, 100\) on a board. Each step: erase two numbers \(a, b\) and write \(|a - b|\). After \(99\) steps, one number remains. Can this number be \(1\)?
📙Intermediate
On a \(3 \times 3\) board with \(+1\) or \(-1\) in each cell, an operation multiplies all entries of a chosen row or column by \(-1\). Starting from all \(+1\)s, can you reach a configuration with exactly one \(-1\)?
📕Advanced
We have coins labeled \(1, 2, \ldots, 2n\). An operation: pick three coins \(a < b < c\) and replace them with \(a+1, b+1, c-2\) (all must remain positive and distinct). Prove no sequence of operations can make all coins equal.