Invariant definition
An invariant is a quantity or property that stays the same under a specified operation or sequence of moves.
Invariant in a picture
How it works
Identify a candidate property and prove that each allowed move preserves it. It then has its starting value after any finite sequence of moves. If a proposed final state has a different invariant, that state cannot be reached by those moves.
Worked examples
Each move changes an integer by 2. What property stays the same?
Parity, since adding or subtracting 2 leaves the remainder modulo 2 unchanged.
Does reordering a list change its sum?
No. The total sum is invariant under a permutation.
Can a sequence of moves that preserves parity take 4 to 9?
No. The start is even and the target is odd.
Common mistake
Name the allowed operations. A quantity can be invariant under one kind of move and change under another.
Quick check
What does a different target invariant imply?
Show answer
The target cannot be reached through the allowed moves.
Can a property such as parity be an invariant?
Show answer
Yes.
Sources
Flashcard
Invariant
Reveal the definition
An invariant is a quantity or property that stays the same under a specified operation or sequence of moves.
Effortless Math. “Invariant.” Math Dictionary.
