08 Invariance

Discovering an invariant in a problem can lead to a simple resolution of an otherwise intractable problem. The method of invariance applies in a situation where a system changes from state to state according to various rules, and some property which is important to the statement of the problem remains unchanged in each transition. The property which doesn't change is known as the invariant.

One of the basic invariants might be the existence of an object which can be observed to be always even or always odd. Problems associated with this idea are sometimes known as parity problems. An Example, from the AMC Primary paper of 2008, is

Example 8.1

At half-time in a soccer match between Newcastle and Melbourne, the score was Newcastle 1, Melbourne 0. Three goals were scored in the second half. Which of the following could not be the result of the match?

(A) The match was drawn (B) Newcastle won by 2 goals

(C) Melbourne won by 2 goals (D) Newcastle won by 1 goal

(E) Newcastle won by 4 goals

Strategy and Solution 8.1

This problem looks like a parity one. Note that at half time the total number of goals is odd. Each goal after that changes the parity of total goals in the match, so three goals change the total to even. And if the total is even, the difference between the teams’ goal count must be even. The only proposed answer in which the difference is odd is (D), hence the answer is (D).

Development

This method of invariance in greater generality is very well illustrated by the following famous problem from the International Mathematics Tournament of Towns, not just for its mathematical properties, but for other various associated aesthetic features.

Example 8.2

On the island of Camelot live 13 grey, 15 brown and 17 crimson chameleons. If two chameleons of different colours meet, they both simultaneously change colour to the third color (e.g. if a grey and brown chameleon meet they both become crimson). Is it possible they will all eventually be the same colour?

Strategy

At first sight this problem looks very difficult, and the imagining of two chameleons with dull colours touching noses becoming a bright colour is also a distraction. With problems like this one should either try to solve a simpler version first, or play around with it by going through a few phases looking at what happens in various phases looking for a successful solution. Doing this can cause frustration after a while as the answer is no and one can go for some time not being able to find a successful pathway.

This is also a case where working backwards can provide a key. Since there are 45 chameleons altogether, a successful answer would be 45 of one colour, none of the other two. Working backwards (as in Chapter 07), in one step gives a configuration 1, 1, 43 (it doesn’t matter which are which colours), then maybe 2, 2, 41, and others might be 3, 3, 39 or 1, 4, 40. Eventually one frequently often recognises a case in which all are multiples of 3. After further exploration, working backwards, one eventually notices that all configurations working backwards have all three the same value modulo 3, whereas in our case our starting configuration has the three different values modulo 3. One then notices that during one nose-touch one colour increases by two (the two chameleons touching) whereas each of their colours has decreased by one, and that whatever happens, in one nose-touch the population of each colour will always involve each of the three numbers modulo 3, so the outcome with all three being zero modulo 3 is not possible.

Solution 8.2

The starting configuration has populations 0, 1, and 2 modulo 3. This situation remains invariant no matter which two chameleons touch noses. So the desired configuration, which has all three equal to zero modulo 3 is not possible.

Comment

I now present another of the wonderful Tournament of Towns problems, one which was set in 1981. I have found this one on many occasions a great one for workshopping with teachers as it lends itself to gradual development in interactive mode.

Example 8.3

On an infinite `squared' sheet six squares are shaded as in the diagram. On some squares there are pieces. It is possible to transform the positions of the pieces according to the following rule: if the neighbour squares to the right and above a given piece are free, it is possible to remove this piece and put pieces on these free squares.

The goal is to have all the shaded squares free of pieces. Is it possible to reach this goal if

1. In the initial position there are 6 pieces and they are placed on the 6 shaded squares?
2. In the initial position there is only one piece, located in the bottom left shaded square?

(composed by M Kontsevich, Moscow)

Solution 8.3

We seek an invariant amidst the continually changing configuration of the pieces on the infinite board. We shall assign a value to a piece according to its location. In one move, some piece is replaced by two others. If we want the total value of the pieces to remain constant, one way is to arrange for each of the new pieces to have a value half that of the one they replace.

Since the value depends not on the piece but its location, we can equivalently assign values to the squares as shown below.

The total value of the squares in the first column, counting from the left, is

1 + ¹/₂ + ¹/₄ + ... = 2.

The total value of each subsequent column is half that of the preceding one. Hence the total value of the squares on the board is

2 + 1 + ¹/₂ + ... = 4.

The total values of the squares in Zone A (the shaded region) are

1 + ¹/₂ + ¹/₂ + ¹/₄ + ¹/₄ + ¹/₄ = 2³/₄,

those in Zone B are

¹/₈ + ¹/₁₆ + ¹/₃₂ + ... = ¹/₄,

those in Zone C are also ¹/₄, and those in Zone D are

4 - 2³/₄ - ¹/₄ - ¹/₄ = ³/₄.

1. Initially, the six pieces have total value 2³/₄. Suppose it is possible to clear Zone A after a finite number of moves. At that point, the total value of the pieces on the board is less than 4 - 2³/₄ = 1¹/₄. This represents a drop in their total value, which should remain constant. We have a contradiction.
2. Initially, the lone piece has value 1. Suppose it is possible to clear Zone A after a finite number of moves. At that point, there is precisely one piece in Zone B, with value at most ¹/₈, and precisely one piece in Zone C, which also has value at most ¹/₈. The remaining pieces are in Zone D. Hence the total value of all the pieces on the board then is less than ¹/₈ + ¹/₈ + ³/₄ = 1. Again we have a contradiction.

(This solution, presented by Jordan Tabov and Andy Liu, is based on the idea given by NN Konstantinov in his talk at the first WFNMC Conference in Waterloo, August, 1990.)