Problem Solving

Invariant

Students rearrange green and orange tiles while keeping the same collection.

Invariant definition

An invariant is a quantity or property that stays the same under a specified operation or sequence of moves.

In Spanish
invariante
Topic
Proof techniques

Invariant in a picture

Invariant diagramSwapping two tiles preserves the number of orange tiles in the collection.Start with two orange tilesCount the property you want to trackSwap any two tile positionsOnly the positions changeThe orange count is still twoEvery allowed swap preserves it
Swapping two tiles preserves the number of orange tiles in the collection.

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 must you show for each allowed move?

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.