Invariants

One generally useful technique in handling combinatorial problems is to make use of numbers associated to the configurations which the problem is dealing with. These numbers are called invariants. Often you can show that the configurations can be manipulated somehow in order to reduce or increase the chosen invariant. This is used when we want to show that you can produce a configuration of a certain type, by illustrating that the invariant can be change to match the requirements. We saw this in several examples at camp.

Perhaps equally commonly, invariants are used to show that something can't be accomplished. That is you show that the invariant of the goal configuration has some property (often parity) which can't occur from manipulations of the current value of the invariant. A trivial example of this would be the standard problem of whether a chessboard with two diagonally opposite corners removed can be tiled with dominoes. If we look at an invariant associated with any partial tiling which we take to be the difference between the number of white squares covered and black squares covered, this must always be 0, since each domino covers one square of each colour. On the other hand in the goal, there are two more squares of one colour than the other, so if there were a tiling, its invariant would be 2. Ergo, impossible.

A number of the problems in the problem set make use of invariants (or can be thought of in that way).