Tricki
a repository of mathematical know-how

Revision of Elementary examples of invariants from Fri, 03/04/2009 - 08:28

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

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

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.