Advanced book on Mathematics Olympiad

1.5 Invariants and Semi-Invariants 19

65.The positive integers are colored by two colors. Prove that there exists an infinite

sequence of positive integersk 1 <k 2 <···<kn<···with the property that the

terms of the sequence 2k 1 <k 1 +k 2 < 2 k 2 <k 2 +k 3 < 2 k 3 <···are all of the

same color.

66.LetP 1 P 2 ...Pnbe a convex polygon in the plane. Assume that for any pair of

verticesPiandPj, there exists a vertexPkof the polygon such that∠PiPkPj=π/3.

Show thatn=3.

1.5 Invariants and Semi-Invariants...................................

In general, a mathematical object can be studied from many points of view, and it is always
desirable to decide whether various constructions produce the same object. One usually
distinguishes mathematical objects by some of their properties. An elegant method is to
associate to a family of mathematical objects aninvariant, which can be a number, an
algebraic structure, or some property, and then distinguish objects by the different values
of the invariant.
The general framework is that of a set of objects or configurations acted on by trans-
formations that identify them (usually called isomorphisms). Invariants then give ob-
structions to transforming one object into another. Sometimes, although not very often,
an invariant is able to tell precisely which objects can be transformed into one another,
in which case the invariant is called complete.
An example of an invariant (which arises from more advanced mathematics yet is
easy to explain) is the property of a knot to be 3-colorable. Formally, a knot is a simple
closed curve inR^3. Intuitively it is a knot on a rope with connected endpoints, such as
the right-handed trefoil knot from Figure 7.

Figure 7

How can one provemathematicallythat this knot is indeed “knotted’’? The answer is,
using an invariant. To define this invariant, we need the notion of a knot diagram. Such a
diagram is the image of a regular projection (all self-intersections are nontangential and
are double points) of the knot onto a plane with crossing information recorded at each
double point, just like the one in Figure 7. But a knot can have many diagrams (pull the
strands around, letting them pass over each other).