Elementary examples of invariants

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. It is a special case of a useful lemma in graph theory: the sum of the degrees of the vertices in a graph must be even (or infinite): we can form a graph by letting the nine people be vertices and joining two of them if and only if they shake hands.

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

Example 2 does not quite fit into the precise general framework of the quick description, because although our operations cannot change quadratic residues into quadratic nonresidues, they certainly can change nonresidues into residues. But it is close enough to the general framework to be included in this article, and indeed the lack of symmetry reflects reality: it is possible to change $6$ into $4$ . Here's one way of doing it: $6\rightarrow 64\rightarrow 15\rightarrow 225\rightarrow 176\rightarrow 127\rightarrow 78\rightarrow 29\rightarrow 841\rightarrow 792\rightarrow\dots\rightarrow 106\rightarrow 57\rightarrow 8\rightarrow 256\rightarrow\dots\rightarrow 11\rightarrow 121\rightarrow 72\rightarrow 23\rightarrow 529\rightarrow\dots\rightarrow 39\rightarrow 1521\rightarrow\dots\rightarrow 2\rightarrow 4.$

Spoiler alert

The next two examples include solutions to two beautiful problems. They are there to illustrate a general principle, but if you have not already seen the solutions, then you should definitely try to solve the problems yourself before reading on. (The fact that the problems are discussed in this article already gives you a clue about how to tackle them.)

Example 3

Tile this depleted grid using 2x1 dominoes

A well known problem asks whether it is possible to tile an eight-by-eight grid with two opposite corners removed using dominoes, if each domino covers two adjacent squares.

This article is part of the "impossibility" branch of the Tricki, so the answer, unsurprisingly, is no. But how does one prove it? More specifically, how would one go about finding an invariant that would allow us to prove it?

The first step is to be clear what our objects and transformation rules are. We don't really have much choice: if we are trying to find a tiling, then the one thing we can do is add or remove dominoes, so that had better be our transformation rule; but if that is the transformation rule, then the "objects" must include arrangements of dominoes. We start with the empty arrangement, and our task is to prove that we cannot create an arrangement that forms what we could call a depleted grid: an eight-by-eight square with two one-by-one squares removed from opposite corners. The depleted grid is therefore another object in our collection (the object that we cannot make), so the obvious definition of "object" is "union of one-by-one squares from the grid".

To solve the problem using invariants, we would like to associate a quantity with arrangements of dominoes, and we would like that quantity to remain the same when we add or remove a domino. The simplest kind of quantity would be a number, and the simplest general way of associating a number with a union of grid squares is to do so in a linear way: that is, we associate a number with each grid square and just add up the numbers associated with the squares in the given union.

If we do that, then how do we ensure that adding or removing a domino makes no difference? We will need the numbers associated with adjacent squares to add up to $0$ . But this more or less determines the numbers: if we arbitrarily choose a number $a$ for one square, then the squares next to it must get $-a$ , and the squares next to them must get $a$ and so on. We end up with a sort of chessboard where the "black" squares get $a$ and the "white" squares get $-a$ .

Does this work? To find out, we need to see what number is associated with the depleted grid. The two removed squares will either both have value $a$ or both have value $-a$ . In the first case, the number we get is $-2a$ and in the second it is $2a$ . (To see this, note that the number associated with an eight-by-eight grid is $0$ , since there are equal numbers of black and white squares.) So if we choose $a$ to be 1, then we have found a domino-adding invariant that takes the value $0$ for the empty arrangement and the value $\pm 2$ for the depleted grid. It follows that we cannot tile the depleted grid with dominoes.

General discussion

The usual way of expressing the above argument makes it seem like a spectacularly clever trick rather than the natural thing to do. One says, "Imagine that the grid is a chessboard. Each domino covers one black square and one white square. But when we remove two opposite corner squares, the number of white squares and the number of black squares differ by $2$ . Therefore, the tiling is impossible."

Each domino necessarily covers 1 dark square and 1 light square.

Example 4

Another well-known problem is to prove that if a rectangle $R$ is tiled with rectangles $R_1,\dots,R_n$ and each $R_i$ has at least one side of integer length, then $R$ has at least one side of integer length.

If we wish to prove this using invariants, then with Example 3 as a model it is natural to treat as our objects all disjoint unions of rectangles whose sides are horizontal and vertical (not worrying too much about what happens at the boundaries). Our basic operation is to add or remove a rectangle with one side of integer length, and we would like to show that it is impossible to get from the empty union to a rectangle that has two sides of non-integer length.

Again it helps to try the simplest sort of invariant: a number $\phi(X)$ that depends additively on the union $X$ of rectangles. (That is, if you take two disjoint shapes $X_1$ and $X_2$ that are both unions of rectangles, then $\phi(X_1\cup X_2)$ should equal $\phi(X_1)+\phi(X_2).$ ) For this to work, we need $\phi(R)$ to be zero for every rectangle $R$ that has an integer side.

The simplest way of associating numbers with subsets of the plane so that they depend additively on the subsets is to take an integrable function $f$ and define $\phi(R)=\int_Rf(x,y)\,dx\,dy.$ (In fact, the Riesz representation theorem implies that a natural generalization of this construction is the only way of defining such a function $\phi$ .) If we do that, then the condition on $\phi$ implies a lot about $f$ . To see this, let us consider a rectangle $R$ of sides $1$ and $\delta$ , where $\delta$ is a small positive number. If the side of length $1$ is the horizontal side, then let $R'$ be the shift of $R$ by $\delta$ to the right.

Another way of creating $R'$ from $R$ is to remove a square $S$ of side $\delta$ from the left of $R$ and add it to the right. Since the integral of $f$ over $R$ needs to be the same as the integral of $f$ over $R'$ (as both need to be zero), the integral over $S$ needs minus the integral over $S+(1,0).$ The obvious way of achieving this (and basically the only way) is to make $f$ have the property that $f(x+1,y)=-f(x,y)$ for every $x$ and $y$ . A similar argument concerning vertical rectangles shows that we should also insist that $f(x,y+1)=-f(x,y)$ for every $x$ and $y$ .

There are many such functions, and most of them turn out to work for this problem. Some people favour $f(x,y)=\sin(\pi x)\sin(\pi y).$ Others prefer to tile the plane with unit squares, colour them black and white as though one had an infinite chessboard, and associate 1 with the black squares and -1 with the white squares. Let us use the second approach.

We now have an invariant, but does it distinguish between the empty set and a rectangle with two non-integer sides? It does, and an easy way to see that it does is to note that $f(x,y)$ can be written as $g(x)g(y)$ , where $g(x)=1$ if the integer part of $x$ is even and $0$ otherwise. If we take the rectangle $R=[a,b]\times [c,d]$ , then we need to calculate $\int_a^bg(x)\,dx\int_c^dg(y)\,dy.$ It is easy to check that both these integrals are non-zero, so their product is non-zero and we are done.

Comments

Though it doesn't really

Mon, 06/04/2009 - 19:09 — Jonah (not verified)

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.

Post new comment

(Note: commenting is not possible on this snapshot.)