Tricki
a repository of mathematical know-how

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.

Prerequisites

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 1 to one person's handshake count without adding 1 to anybody else's. But that is impossible: each handshake adds 1 to the handshake counts of two people.

And now we are a short step away from the proof. If each handshake adds 1 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 3.

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 2 of the total handshake count: that is, the total handshake parity is 1 if the total handshake count is odd and 0 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 x by x^2, 2^x, or x-49. 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 m and look at what happens mod m when one performs the three operations. The smaller m is, the easier this will be to investigate, so let us work upwards.

If we take m=2, 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 m=3 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 m=7. 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 x by x^2 or 2^x?

Let us investigate this in the crudest way possible, by just listing the values of x^2 and 2^x as x goes from 0 to 6. We get 0,1,4,2,2,4,1 for the squares and 1,2,4,1,2,4,1 for the values of 2^x. 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 0, since the only way we have seen of producing 0 is to square 0, so if we start with a number that is not a multiple of 7 then we will never obtain a multiple of 7.)

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 2 is a quadratic residue mod 7.

General discussion

To be continued.

Comments

Though it doesn't really

Though it doesn't really belong in this article, there's a very clever proof of the fourth example (and many similar problems) which should certainly go somewhere in the Tricki. I believe it's called the garden-path argument, though I can't find who invented it.

Given such a tiling of R, create a graph G whose vertices are the corners of the tiles and whose edges connect the corners along the sides of integer length. For tiles with four sides of integer length, just include two parallel sides (it doesn't matter which) as edges in G rather than all four. Now the degree of each vertex is the number of tiles for which it's a corner. It's easy to see that this is 1 for the four corners of R, and 2 or 4 for all other vertices.

If we arbitrarily make a path starting at one of these four corners which repeats no edges, we can only get stuck at another corner, since all other vertices have even degree. So there exists a path between two distinct corners of R which only moves parallel to the sides of R in integral steps, and so at least one side of R has integral length.

One can also use this to prove, for instance, that an m-by-n rectangle can be tiled with 1-by-k polyominoes if and only if k divides m or n.