Tricki

Revision of Elementary examples of invariants from Fri, 03/04/2009 - 10:44

Quick description

If you want to show that one object cannot be transformed into another in a given way, then associate a quantity with each object that does not change when you transform objects in the given way, but which is different for the two objects in question.

Very few.

Example 1

There are nine people in a room, and they start shaking hands. Is it possible that everybody ends up shaking hands with precisely three other people?

If you try to come up with a way for the nine people to do this, you will find that you cannot. But what goes wrong? If you actually make a serious effort to devise a scheme for the handshakes, then you may well discover for yourself: typically you will arrive at a situation where all but one of the people have shaken hands with three others, and the remaining one person has shaken hands with just two others. And then you are stuck because the last person cannot have a third handshake without giving somebody else a fourth handshake.

This does not yet prove anything – for that one needs to argue that one will always get into this difficult situation – but it gives us a big clue. What goes wrong in an attempt like this is that one finds oneself needing to add to one person's handshake count without adding to anybody else's. But that is impossible: each handshake adds to the handshake counts of two people.

And now we are a short step away from the proof. If each handshake adds to the handshake counts of two people, then the sum of all the handshake counts must always be even. Therefore it is not possible for nine people all to have handshake counts of

General discussion

How does the above example fit the quick description at the beginning of this article? To answer this question we need to think what our "objects" are. We might call them handshake protocols: decisions about who will shake hands with whom. And what are the rules that allow us to transform one handshake protocol into another? There is just one rule: add a handshake. And what is the quantity that does not vary when we apply an allowable transformation? It is the quantity we obtain by adding up the number of times each person has shaken hands and seeing whether the answer is even or odd. We could be more formal about it and define the total handshake count to be the sum of the number of times each person has shaken hands, and define the total handshake parity to be the reduction mod of the total handshake count: that is, the total handshake parity is if the total handshake count is odd and if the total handshake count is even.

The above argument is an example of a parity argument.

Example 2

You are given the number 4 and asked to transform it into the number 6. There are three operations that you are allowed to perform: you can replace by , , or Is it possible to convert 4 into 6 by repeatedly applying these operations (in whatever order and for however long you like)?

If you try this, you may eventually become convinced that it is not possible. But how can one prove that it is impossible? One answer is to try to find some property that 4 has but 6 lacks, and to show that one cannot get rid of that property using any of the three operations that you are allowed.

If you are used to this kind of problem with the integers, then one of the first things you will try is modular arithmetic. The idea to find some number and look at what happens mod when one performs the three operations. The smaller is, the easier this will be to investigate, so let us work upwards.

If we take , then we are simply looking at whether a number is even or odd. Since subtracting 49 changes the parity of a number, we will not be able to draw any conclusions. A similar argument shows that taking is no help: to subtract 49 is to subtract 1 mod 3, so one can get any number mod 3 by repeated subtractions of 49.

After these two examples, it starts to become obvious that the smallest number that has any chance of telling us something useful is 7. So let us see what happens when Now we have "neutralized" the operation of subtracting 49 – it makes no difference mod 7, and this is exactly the kind of thing we want to happen. But what happens if we replace by or ?

Let us investigate this in the crudest way possible, by just listing the values of and as goes from to We get for the squares and for the values of . None of these values is equal to 6, so our problem is solved: if we start with 4, then the only numbers we will ever be able to produce are numbers that are equal to 1, 2 or 4 mod 7. (We cannot get , since the only way we have seen of producing is to square , so if we start with a number that is not a multiple of then we will never obtain a multiple of .)

A slightly more sophisticated way of expressing this proof is to say that our three operations always take quadratic residues to quadratic residues. This is obvious for the first two operations, and true also for the third because is a quadratic residue mod .

To be continued.