Invariants and Monovariants

In one sentence

A process changes at every step, but if some quantity $I$ never changes at any step, then

I (start) = I (every step) = I (end)

The end point is locked by it: states with a different value of $I$ can never be reached. If a quantity never increases (a decreasing monovariant) and is a non-negative integer, the process cannot go on forever; if it never decreases and actually grows, you can never get back to the start. Looking for such a quantity is the first reflex for problems about “operations”.

Predict first

The numbers $1, 2, \dots, 10$ are written on a board. Each time, erase two numbers $a, b$ and write $∣ a - b ∣$ . In the end one number is left. Can it be $0$ ?

YesNo

Choose an answer first; then you can see the result.

Example: 1, 2, 3, 4, 5. Each time, replace a, b by a + b + ab. What is left at the end?

Step 1 / 4

Find the change
$a + b + ab$ looks messy, but add $1$ and it factors: $1 + (a + b + ab) = (1 + a) (1 + b)$ .

$1 + (a + b + ab) = (1 + a) (1 + b)$
The invariant
Any order gives the same
The end

Stop 1 · Periodic sequences (Vol. 5)

If an integer sequence has a bounded invariant, it can only take finitely many states, so it must be periodic.

Example: a₁ = 1, a₂ = 3, aₙ₊₂ = aₙ₊₁ − aₙ. Why is it periodic?

Step 1 / 3

Find an invariant quadratic
Write two neighboring terms as $(a, b)$ ; the next pair is $(b, b - a)$ . Try $Q (a, b) = a^{2} - ab + b^{2}$ :

$Q (b, b - a) = b^{2} - b (b - a) + (b - a)^{2} = a^{2} - ab + b^{2}$
It shuts the states in a finite box
Finite + reversible ⇒ periodic

Stop 2 · Iteration: two means (Vol. 2)

Iterate two numbers at once: one quantity is invariant and two are monotonic, so the limit gets squeezed out.

Example: x₀ = 1, y₀ = 4, xₙ₊₁ = (xₙ + yₙ)/2, yₙ₊₁ = 2xₙyₙ/(xₙ + yₙ)

Step 1 / 3

The invariant
The arithmetic mean times the harmonic mean:

$x_{n + 1} y_{n + 1} = \frac{x _{n} + y _{n}}{2} \cdot \frac{2 x _{n} y _{n}}{x _{n} + y _{n}} = x_{n} y_{n} = 4$
The monovariants
Squeeze out the limit

Stop 3 · Rotating the axes: invariants of a conic (Vol. 7)

When the coordinate axes are rotated, the coefficients of $A x^{2} + B x y + C y^{2}$ all change, but $A + C$ and $B^{2} - 4 A C$ do not.

Example: what curve is 5x² + 4xy + 2y² = 6?

Step 1 / 3

Two invariants
After rotating to remove the $x y$ term we get $λ_{1} x^{'2} + λ_{2} y^{'2} = 6$ . The invariants give:

$λ_{1} + λ_{2} = A + C = 7, - 4 λ_{1} λ_{2} = B^{2} - 4 A C = - 24$
Solve for the new coefficients
Read off the curve

Stop 4 · An increasing monovariant: no way back (Vol. 5)

Infinite descent says that a positive integer cannot decrease forever. In the other direction, a quantity that strictly increases means you can never return to the start.

Each time, replace

a, b

a + b

and

∣ a - b ∣

. Make a few moves: how does

\sum x^{2}

change? Can you get back to

3, 4, 12

One problem, several solutions

The board shows $3, 4, 12$ . Each time, replace two numbers $a, b$ by $a + b$ and $∣ a - b ∣$ . Can $3, 4, 12$ appear again after some moves (at least one)?

Sum of squares: an increasing monovariant

$(a + b)^{2} + (a - b)^{2} = 2 (a^{2} + b^{2})$ , so a move increases $\sum x^{2}$ by $a^{2} + b^{2} \geq 0$ : it never decreases. In the first move both numbers are positive, so $\sum x^{2}$ becomes strictly larger than $169$ ; after that it never decreases, so it can never return to $3^{2} + 4^{2} + 1 2^{2} = 169$ . Answer: no.

CostOnce you find Σx², you are done.

The sum: another increasing monovariant

The new sum is $(a + b) + ∣ a - b ∣$ , which is $∣ a - b ∣ \geq 0$ more than before, so the sum never decreases either. The starting numbers $3, 4, 12$ are pairwise different, so after the first move the sum is strictly larger than $19$ ; it never decreases after that, so again there is no way back.

CostWorks just as well, but watch out: it does not grow when the two numbers are equal.

Practice

Exercise 1Basic

The numbers $1, 2, \dots, 10$ are written on a board. Each time, erase two numbers $a, b$ and write $∣ a - b ∣$ , until one number is left. What is its remainder on division by $2$ ?

Exercise 2Basic

The numbers $1, 2, \dots, 9$ are written on a board. Each time, erase two numbers $a, b$ and write $a + b + ab$ . What number is left at the end?

Exercise 3Advanced

The numbers $1, \frac{1}{2}, \frac{1}{3}, \dots, \frac{1}{6}$ are written on a board. Each time, erase two numbers $a, b$ and write $\frac{ab}{a + b}$ . What number is left at the end?

Exercise 4Challenge

Rotating the coordinate axes turns the curve $x^{2} + 4 x y + y^{2} = 3$ into $λ_{1} x^{'2} + λ_{2} y^{'2} = 3$ . Find $λ_{1} λ_{2}$ and decide what type of curve it is.

In one sentence

Example: 1, 2, 3, 4, 5. Each time, replace a, b by a + b + ab. What is left at the end?

Stop 1 · Periodic sequences (Vol. 5)

Example: a₁ = 1, a₂ = 3, aₙ₊₂ = aₙ₊₁ − aₙ. Why is it periodic?

Stop 2 · Iteration: two means (Vol. 2)

Example: x₀ = 1, y₀ = 4, xₙ₊₁ = (xₙ + yₙ)/2, yₙ₊₁ = 2xₙyₙ/(xₙ + yₙ)

Stop 3 · Rotating the axes: invariants of a conic (Vol. 7)

Example: what curve is 5x² + 4xy + 2y² = 6?

Stop 4 · An increasing monovariant: no way back (Vol. 5)

Sum of squares: an increasing monovariant

The sum: another increasing monovariant

Practice

Mistake Museum · Exhibits from this stop

The invariant does not object, so it must be possible

Taking a quantity that changes for an invariant

Stops on this line