Algorithms and processes
Abhay B
May 2021
§1 Introduction
We are often given an algorithm in a combinatorics question. That is, we a set of states is defined,
along with a function from that set to itself. Then we run this function many times. We need
to prove something is/is not possible. There are a few tools to analyse such processes. Invari-
ants/Monovariants are very useful for this. The Extremal principle is another very important
idea.
Both these ideas have something in common intuitively- you don’t need to understand everything
that’s going on perfectly More often than not, you only need a part of the structure of the question.
§2 Problems
Remark 1 (Invariants)
If things are changing, see what is not changing
More often than not in such questions, we are given local information, i.e the rule that takes one
state to another, and are asked to prove global information, for example, judging how the initial
state affects the final one, or to describe the long term behavior of the function.
Invariants are useful because they constraint the conditions on the final state given a initial state.
Remark 2 (Lemma X)
If there are only finitely many possible states an algorithm can reach, then the process must
eventually repeat or stay constant
1
2
Example 1
There are a white, b black, and c red chips on a table. In one step, you may choose two chips
of different colors and replace them by a chip of the third color. If just one chip will remain at
the end, its color will not depend on the evolution of the game. When can this final state be
reached?
Example 2
Several positive integers are written on a blackboard. One can erase any two distinct integers and
write their greatest common divisor and least common multiple instead. Prove that eventually
the numbers will stop changing.
We can generalise the use of algorithms by introducing them ourselves. When we are given a set
of states in the question, we can make an algorithm ourselves to prove what is required. One use is
to find a construction. If we are trying to prove there always exists a state such that some condition
is satisfies, then one way is to find an algorithm that takes some (possibly random, or maybe a
fixed )state to one that works. This could also be used to prove a contradiction sometimes.
Example 3 (Putnam 1979)
There are n red and n blue points in the plane. Is it always possible to join them with n segments
such that each segment connects one red and one blue vertex,all vertices are covered and no two
segments intersect?
The Extremal principle is more of a guideline. It says that when we have a bunch of states its a
nice idea to look at at the most ”extreme” of these and follow these through the process. Sometimes
the value from which we call something ”extreme” is obvious- for example in a tuple of numbers.
Other times we need to impose such a ordering.
Example 4
The n cards of a deck (where n is an arbitrary positive integer) are labeled 1, 2, ..., n. Starting
with the deck in any order, repeat the following operation: If the card on top is labeled k, reverse
the order of the first k cards. Prove that eventually the first card will be 1 (so no further changes
occur).
3
Example 5
A finite graph G is drawn on a blackboard. The following operation is permitted: pick any cycle
of C of G, draw a new vertex v, connect it to all vertices of C, and finally erase all the edges of
C. Prove that this operation can only be done a finite number of times.
Read Greedy algorithms for another use of processes. Also, quite often induction feels like an
algorithm.