Invariants

Change is Not the Only Constant
Online Math Club
Rajdeep Ghosh
October 16, 2021
This talk is centred around the idea of invariants followed by ideas related to monovariants.
§1 The Invariance Principle

Copying shamelessly from Arthur Engel, we state the idea :
If there is repetition, look for what does not change
Expanding on this, the idea is that whenever a (often iterative) transformation is applied to a system
repeatedly, looking for what does not change helps us predict these unchanged properties in the future
states, by looking at the same properties in the start state.
This idea is very fundamental and hence shows up a lot throughout math.
The invariance principle is what we call a heuristic principle. Put simply, it means there is no way to
learn it except by solving problems involving it. So, wasting no time, we jump into the problems!
(A major subset of the problems here are from Problem Solving Strategies by Arthur Engel. If you
already know all the solutions to the problems here, I sincerely hope that you take away something new
from this talk nonetheless.)
§1.1 Problems on Invariants

Problem 1.1 (Engel E2). Suppose the positive integer n is odd. First Al writes the numbers 1, 2, . . . , 2n
on the blackboard. Then he picks any two numbers a, b, erases them, and writes, instead, |a − b|. Prove
that an odd number will remain at the end.
Problem 1.2 (Engel E3). A circle is divided into six sectors. Then the numbers 1, 0, 1, 0, 0, 0 are written
into the sectors (counterclockwise, say). You may increase two neighboring numbers by 1. Is it possible
to equalize all numbers by a sequence of such steps?
Problem 1.3 (Engel E7). Each of the numbers a1 , . . . , an is 1 or −1, and we have
S = a1 a2 a3 a4 + a2 a3 a4 a5 + · · · + an a1 a2 a3 = 0
Prove that 4|n.
Problem 1.4 (Engel P2). Start with the set {3, 4, 12}. In each step you may choose two of the numbers
a, b and replace them by 0.6a − 0.8b and 0.8a + 0.6b. Can you reach the goal (a) or (b) in finitely many
steps:
√
(a) {4, 6, 12}, (b) {x, y, z} with |x − 4|, |y − 6|, |z − 12| each less than 1/ 3.
1
Rajdeep Ghosh (October 16, 2021) Change is Not the Only Constant
Problem 1.5 (Engel P11). In the given figure, you may switch the signs of all numbers of a row, column,
or a parallel to one of the diagonals. In particular, you may switch the sign of each corner square.
Prove that at least one -1 will remain in the table.
Problem 1.6. Let S be a set of numbers. If a, b ∈ S, we can add ab + a + b to S. Initially S = {2, 3, 4, 5}.
Is it possible that after a series of such operations 3023 ∈ S?
The only morally correct way to stop talking about invariants is to refer to the famous windmill problem
from IMO 2011.
Problem. Let S be a finite set of at least two points in the plane. Assume that no three points of S are
collinear. A windmill is a process that starts with a line ` going through a single point P ∈ S. The line
rotates clockwise about the pivot P until the first time that the line meets some other point belonging to
S. This point, Q, takes over as the new pivot, and the line now rotates clockwise about Q, until it next
meets a point of S. This process continues indefinitely. Show that we can choose a point P in S and a line
` going through P such that the resulting windmill uses each point of S as a pivot infinitely many times.
For the inquisitive among you, I’m linking 3Blue1Brown’s beautiful solution video to this equally
beautiful problem.
§2 Monovariants
The idea of monovariants is a closely related one to that of invariance, in the sense that there is a
process(which is often iterative) and we would like to make some predictions regarding its future states.
It differs in principle with invariance as the latter deals with functions of the state whose value re-
mains unchanged as the state is transformed, whereas the former deals with functions of states whose
value changes monotonically(i.e - continuous non-decrease or non-increase) as the state is transformed.
Just like invariance, the principle of monovariance is also a heuristic one, and hence the only way
to understand and appreciate it is through problem solving. Let’s get into the problems!
§2.1 Problems on Monovariants

Problem 2.1. 2000 people are distributed among the rooms of a 115-room mansion. Each minute, as
long as not all the people are in the same room, somebody walks from one room into a different room
with at least as many people. Prove that eventually all the people will be gathered in one room
Problem 2.2 (Engel E4). In the Parliament of Sikinia, each member has at most three enemies. Prove
that the house can be separated into two houses, so that each member has at most one enemy in his own
house.
Problem 2.3 (Engel E8). 2n ambassadors are invited to a banquet. Every ambassador has at most
n − 1 enemies. Prove that the ambassadors can be seated around a round table, so that nobody sits next
to an enemy.
Problem 2.4 (Engel E10). Start with a tuple S = (a, b, c, d) of positive integers and find the derived
tuple S1 = T (S) = (|a − b|, |b − c|, |c − d|, |d − a|). Does the sequence S, S1 , S2 = T (S1 ), S3 = T (S2 ), . . .
always end up with (0, 0, 0, 0)?
Problem 2.5 (Stanford Putnam Training 2007). On an n × n board, there are n2 squares, n − 1 of which
are infected. Each second, any square that is adjacent to at least two infected squares becomes infected.
Show that at least one square always remains uninfected.

Invariants

Uploaded by

Copyright:

Available Formats

Invariants

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Invariants

Uploaded by

Copyright:

Available Formats

Change is Not the Only Constant

Online Math Club

§1 The Invariance Principle

If there is repetition, look for what does not change

§1.1 Problems on Invariants

Prove that 4|n.

§2.1 Problems on Monovariants

You might also like