MATC44H3 Chap.6 The Invariance Principle
The Invariance Principle
What does not change
The invariance principle applies to processes that repeat a move. Find a quantity that no move can change; if it takes different values at the start and at a desired end, the end can never be reached.
The lecture quotes Arthur Engel's advice to look for what does not change whenever there is repetition, and restates the domino fact of the colouring lecture as an invariant: the difference between dark and light squares covered stays at zero.
Two lecture examples
In the first, six numbers sit in the sectors of a circle and a move adds 1 to two neighbours.
The alternating sum of the six numbers is invariant, because neighbours carry opposite signs; it starts at 2 and would be 0 if all numbers were equal, so equalising is impossible. In the second, the numbers 1 to 200 are on a blackboard and a move replaces two numbers by their sum.
The total never changes, so the last number must be the starting total, 20,100.
Weaker invariants
When the exact value of a quantity changes, its remainder on division by 2 or by another number may still be preserved. Parity invariants settle many questions about flipping coins, replacing numbers by differences, and moving pieces on a board.
The first assignment asks a question of this kind about coins arranged in a circle. An invariant can only prove impossibility; showing that a target can be reached needs an explicit sequence of moves.
What this chapter covers
- 01
Quantities preserved by a repeated move
- 02
Alternating sums on a circle
- 03
Sums on a blackboard
- 04
Parity as a weaker invariant
- 05
Restating colouring proofs as invariants
- 06
Why equal invariants prove nothing
Worked example · free
Flipping two neighbouring cups
- 2Let U be the number of upside-down cups. A move changes U by +2, 0 or −2.
- 1So the parity of U never changes; it starts at 0, which is even.
- 1All seven upside down needs U = 7, which is odd, so it can never be reached.
Key terms
- Invariance Principle
- The invariance principle says that a quantity unchanged by every move takes the same value at every stage of a process.
- Alternating Sum
- An alternating sum adds and subtracts terms in turn, as in a1 − a2 + a3 − a4.
- Parity Invariant
- A parity invariant is a quantity whose remainder on division by 2 no move can change.
- Reachable State
- A reachable state is a configuration that some finite sequence of allowed moves produces from the start.
The Invariance Principle FAQ
What makes a good invariant?
A good invariant is simple to compute, unchanged by every allowed move, and different at the start and at the target. Sums, alternating sums, counts of a colour and parities are the usual candidates. Test a candidate on one move algebraically before building the argument on it.
Can an invariant prove that a target is reachable?
No. If the start and the target share the invariant's value, the argument says nothing either way. To show a target can be reached you must give an explicit sequence of moves, as with any construction question.
How is invariance related to colouring proofs?
A colouring proof counts colours in a finished arrangement, while an invariance proof follows a quantity through each move. Placing tiles one at a time turns the first into the second: the difference between colours covered is a quantity each tile leaves unchanged.
What quantities should I try first when looking for an invariant?
Start with the simplest: the total of all the numbers, an alternating sum around a circle, the number of objects of one colour or state, and the remainders of these on division by 2 or 3. Compute how one move changes each candidate, and keep the one that never changes.
Exam move
Collect three processes from the course materials and one of your own, and for each write the move, the invariant, its start value and its target value. Then take a target that shares the invariant's value and try to reach it, so that you remember that an invariant can only prove impossibility.
Working through The Invariance Principle in MATC44H3? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 The Invariance Principle question and get a clear, step-by-step explanation grounded in how MATC44H3 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
