Math396 Invariants and Semi-Invariants Examples

Stephen New

The numbers \(1,2,3,\dotsc,30\) are written on a blackboard. At each step we perform the following action: choose any two of the numbers \(a\) and \(b\), erase them, and then write the number \(|a-b|\) on the board. Continuing this until only a single number remains, is it possible that the last number is \(8?\)

Solution

Realize that the action in this situation, replacing two numbers with the distance between them, preserves the parity (even-/odd-ness) of the sum of those numbers. Because of this, it’ll preserve the parity of the sum of all the numbers on the board. The parity of this sum is an invariant in this situation. Since \(1+2+\dotsb +30\) is odd (there are an odd number of odd summands), the final remaining number must be odd too, and can’t be \(8\).

MathSE

Start with the triple \((3, 4, 12)\). You may take the following action to update the triple: choose any two numbers within the triple, \(a\) and \(b,\) and replace them by the numbers \(\frac{4a}{5} + \frac{3b}{5}\) and \(-\frac{3a}{5} + \frac{4b}{5}.\) Can you reach the triple \((4, 6, 12)\) by applying this action finitely many times?

Solution

Thinking geometrically about what the action is doing to the point \((3, 4, 12)\) in space, realize that the action preserves a point’s distance from the origin. Since \(3^2 + 4^2 + 12^2 = 169\) but \(4^2 + 6^2 + 12^2 \neq 169\), you can never reach that triple by iteratively taking that action.

A clue towards the geometric interpretation of the situation is that the numbers \(3\), \(4\), and \(5\) that appear in the action are a Pythagorean triple, and \(\left(\frac{3}{5}\right)^2 + \left(\frac{4}{5}\right)^2 = 1\). The action itself may look familiar from a class on linear algebra or multi-variable calculus: it’s a rotation. \[ \begin{pmatrix} 4/5 & 3/5 \\ -3/5 & 4/5 \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} \] Specifically it’s a rotation by \(\arctan(3/4)\) around the coordinate axis of whatever two coordinates you chose, and so the action preserves distance from the origin: the invariant is the point’s distance from the origin. The initial point \((3,4,12)\) is \(13\) from the origin, and the target point is not.

A chocolate bar is a \(3 \times 4\) grid of small rectangles. What is the minimum number of times you’d need to snap a chocolate piece along a grid line before you have \(12\) individual rectangles?

Solution

Notice that each time you snap a chocolate piece, the total number of pieces increases by one. Since you turning one piece into twelve pieces, eleven snaps are required. The fact that each snap increases the number of pieces by one is the semi-invariant (or mono-invariant) of the action.

AoPS

On the surface of the sun is a very peculiar sort of alien. There are thirteen of them total, and they are one of three colors: blue, orange, and white. Right now three are blue, four are orange, and six are white. They bumble about the surface of the sun and occasionally they bump into each other. If two aliens of different colors collide, they both change into the third color. E.g. if a blue alien and white alien collide, they’ll both turn orange. Can the aliens ever all be blue?

Solution

Nope. There are a few ways to see this. One way is by noticing the fact that the difference between the numbers of blue and white aliens will always be a multiple of three. The fact that the bumping move preserves this is our invariant. The condition that all thirteen aliens are blue (and zero aliens are white) does not meet this condition.

To prove this fact, let \(b\) be the number of blues and \(w\) be the number of whites. Initially \(b=3\) and \(w=6\), so \(b-w\) is a multiple of three. If a blue and white bump into each other, \(b \to b-1\) and \(w \to w-1,\) preserving their difference. If a blue and orange bump then \(b \to b-1\) and \(w \to w+2\), changing the difference by a summand of three. If a white and orange bump then \(w \to w-1\) and \(w \to w+2\), changing the difference by a summand of three.

Stephen New

Show that if \(25\) competitors play in a ping pong tournament, then, by the end of the tournament, the number of competitors who played an even number of matches is odd.

Solution

Every match involves two competitors. Let \(n_i\) be the number of matches that competitor \(i\) played in. If there are \(N\) matches played total, then \[n_1 + n_2 + \dotsb + n_{25} = 2N\,.\] In particular that sum is even. (The invariant here is the evenness/oddness of that sum) Since that sum is even, an even number of the summands must be odd.

Polya Seminar

Right now, on an \(n \times n\) chessboard consisting of \(n^2\) squares, \(n-1\) of the squares are infected. Each second, any square that is adjacent to at least two infected squares will itself become infected. Show that at least one square always remains uninfected.

Solution

Working through cases, one could come up with various arguments why a single square will always remain uninfected. Noticing the semi-invariant in this case simply gives us a more elegant argument.

Notice that the perimeter of the initial infected region is \(4(n-1),\) and that by the rule, after each second, the perimeter of the infected region cannot increase; this serves as our semi-invariant. Since the perimeter of the whole chessboard is \(4n\) the infected region will never encompass the whole board, necessitating at least one uninfected square.