1.5 Invariants and Semi-Invariants 21less well-known mathematician Gerwin proved that given two polygons of equal area,
the first can be dissected by finitely many straight cuts and then assembled to produce
the second polygon. In his list of 23 problems presented to the International Congress
of Mathematicians, D. Hilbert listed as number 7 the question whether the same prop-
erty remains true for solid polyhedra of the same volume, and if not, what would the
obstruction be.
The problem was solved by M. Dehn, a student of Hilbert. Dehn defined an invariant
that associates to a finite disjoint union of polyhedraPthe sumI(P)of all their dihedral
angles reduced modulo rational multiples ofπ(viewed as an element inR/πQ). He
showed that two polyhedraP 1 andP 2 having the same volume can be transformed into
one another if and only ifI(P 1 )=I(P 2 ), i.e., if and only if the sums of their dihedral
angles differ by a rational multiple ofπ.
It is good to know that the quest for invariants dominated twentieth-century geometry.
That being said, let us return to the realm of elementary mathematics with a short list
problem from the 46th International Mathematical Olympiad.
Example.There arenmarkers, each with one side white and the other side black, aligned
in a row with their white sides up. At each step, if possible, we choose a marker with
the white side up (but not one of the outermost markers), remove it, and reverse the two
neighboring markers. Prove that one can reach a configuration with only two markers
left if and only ifn−1 is not divisible by 3.
Solution.We refer to a marker by the color of its visible face. Note that the parity of
the number of black markers remains unchanged during the game. Hence if only two
markers are left, they must have the same color.
We define an invariant as follows. To a white marker withtblack markers to its left
we assign the number(− 1 )t. Only white markers have numbers assigned to them. The
invariantSis the residue class modulo 3 of the sum of all numbers assigned to the white
markers.
It is easy to check thatSis invariant under the operation defined in the statement.
For instance, if a white marker withtblack markers on the left and whose neighbors are
both black is removed, thenSincreases by−(− 1 )t+(− 1 )t−^1 +(− 1 )t−^1 = 3 (− 1 )t−^1 ,
which is zero modulo 3. The other three cases are analogous.
If the game ends with two black markers thenSis zero; if it ends with two white
markers, thenSis 2. This proves thatn−1 is not divisible by 3.
Conversely, if we start withn≥5 white markers,n≡0 or 2 modulo 3, then by
removing in three consecutive moves the leftmost allowed white markers, we obtain a
row ofn−3 white markers. Working backward, we can reach either 2 white markers
or 3 white markers. In the latter case, with one more move we reach 2 black markers as
desired.
Now try to find the invariants that lead to the solutions of the following problems.