Invariance and Symmetry

The Putnam disguises invariants inside algebra: "the operation replaces $(a, b)$ by $(a + b, ab)$… show some value is never reached" is an invariant problem, and the invariant is often a symmetric function of the pair (here $a + b - ab$ is not preserved, but $(a - 1)(b - 1)$ maps to $(a + b - 1)(ab - 1)$ — try several candidates). The systematic search: write the move algebraically and test the elementary symmetric functions, discriminants and determinants.

When the question is "show the process stops" rather than "show the state is unreachable", look for a monovariant. The classic: $n$ people around a table pass coins; the sum of squares of holdings strictly decreases with each legal move, so the process ends. Strict decrease of a non-negative integer is a proof of termination in one sentence.

Symmetry arguments give integrals for free (King's rule), pair off terms in sums (roots of unity, $k \leftrightarrow n - k$), and settle games (the second player mirrors). The failure mode is assuming the extremum is at the symmetric point without proof: symmetry says the symmetric point is a critical point, not that it is the maximum. Check.

The proof is an induction on the number of moves: if each move preserves $I$, so does every sequence of moves, so every reachable state has $I = I(\text{start})$. Finding $I$ is the whole problem. Write the move algebraically and test the natural candidates on it: the sum, the sum of squares, a product, a residue, a discriminant. For a tiling, the "move" is placing one tile, and the invariant is a weighting of the cells that every tile placement covers with the same total weight.

Step 1 — test the sum of squares on one move: $\left(\tfrac{a+b}{\sqrt2}\right)^2 + \left(\tfrac{a-b}{\sqrt2}\right)^2 = \tfrac{2a^2 + 2b^2}{2} = a^2 + b^2$. The other eight numbers are untouched, so the sum of squares of all ten numbers is invariant.

Step 2 — at the start it is $1^2 + 2^2 + \cdots + 10^2 = 385$.

Step 3 — ten numbers of absolute value less than $6$ have sum of squares less than $10\cdot36 = 360 < 385$. So the answer is no.

How to find it. The move is a rotation of the pair $(a, b)$ by $45^\circ$ (its matrix is orthogonal), and rotations preserve length: the sum of squares is the first thing to try.

Step 1 — compute the moves on $f = ax^2 + bx + c$. First: $x^2f\!\left(\tfrac1x + 1\right) = a(1 + x)^2 + bx(1 + x) + cx^2 = (a + b + c)x^2 + (2a + b)x + a$. Second: $(x - 1)^2f\!\left(\tfrac{1}{x-1}\right) = a + b(x - 1) + c(x - 1)^2 = cx^2 + (b - 2c)x + (a - b + c)$.

Step 2 — discriminants: $(2a + b)^2 - 4a(a + b + c) = b^2 - 4ac$, and $(b - 2c)^2 - 4c(a - b + c) = b^2 - 4ac$. Both moves preserve the discriminant.

Step 3 — $x^2 + 4x + 3$ has discriminant $16 - 12 = 4$ and $x^2 + 10x + 9$ has $100 - 36 = 64$. Unreachable.

How to find it. Track the roots: if $f(r) = 0$, the first new polynomial vanishes at $\tfrac{1}{r - 1}$ and the second at $1 + \tfrac1r$. The discriminant is $a^2(r_1 - r_2)^2$, and under $r \mapsto \tfrac{1}{r-1}$ the root difference is divided by $(r_1 - 1)(r_2 - 1)$ exactly as the new leading coefficient $a + b + c = f(1) = a(1 - r_1)(1 - r_2)$ multiplies it. Quantities built from root differences are the natural invariants of substitutions.

Step 1 — number rows and columns $0$ to $9$ and give cell $(i, j)$ the colour $(i + j) \bmod 4$.

Step 2 — a horizontal tile covers $(i, j), \ldots, (i, j+3)$, whose values of $i + j$ are four consecutive integers, one in each residue class mod $4$; the same holds for a vertical tile. So every tile covers exactly one cell of each colour.

Step 3 — a tiling uses $\tfrac{100}{4} = 25$ tiles and would cover exactly $25$ cells of each colour.

Step 4 — count: the number of cells with $i + j = s$ is $s + 1$ for $s \le 9$ and $19 - s$ for $s \ge 9$. Colour $1$ gets $s = 1, 5, 9, 13, 17$: $2 + 6 + 10 + 6 + 2 = 26 \ne 25$. No tiling exists. (The other colours get $25$, $25$, $24$.)

How to find it. Area alone ($100 = 25\cdot4$) is no obstruction, so the invariant must see position. A colouring adapted to the tile — period $4$ along both rows and columns — is the finest one every tile treats identically. The general theorem (de Bruijn): an $m\times n$ board tiles by $1\times k$ bars iff $k \mid m$ or $k \mid n$.

A strictly monotone quantity never returns to an earlier value, so no state repeats. If there are finitely many possible values, the sequence of values, and hence of moves, is finite; with nonnegative integer values decreasing by at least $1$, the starting value itself bounds the number of moves. The creative step is the choice of $M$: a total, an energy, a count of "bad" pairs. Test it on the move and compute the change exactly; its sign should be forced by the very condition that makes the move legal.

Step 1 — the monovariant is the total sum $T$ of the table. Flipping a line whose sum is $s < 0$ changes that line's contribution from $s$ to $-s$ and leaves everything else alone, so $T$ increases by $-2s > 0$.

Step 2 — each entry is always $\pm$ its original value, so there are at most $2^{mn}$ possible tables, and $T$ takes at most $2^{mn}$ values.

Step 3 — a strictly increasing sequence in a finite set is finite, so the process stops.

Step 4 — it stops exactly when no line has a negative sum, which proves the second claim (just keep flipping). $\blacksquare$

How to find it. The legal move is triggered by a negative sum, and flipping it turns a negative contribution into a positive one: the sum itself is the quantity the move improves. Finiteness of the state space replaces any need for integer values.

Step 1 — start from any colouring, and let $M$ be the number of monochromatic edges (both ends the same colour).

Step 2 — call a vertex $v$ bad if more than half of its $d$ neighbours share its colour: say $p$ of them do and $q = d - p$ do not, with $p > q$. Switch the colour of $v$. Its $p$ monochromatic edges become bichromatic and its $q$ bichromatic edges become monochromatic; no other edge changes. So $M$ drops by $p - q \ge 1$.

Step 3 — $M$ is a nonnegative integer, so after at most $|E|$ switches no bad vertex remains, and that colouring has the property. $\blacksquare$ (Equivalently: a colouring with the FEWEST monochromatic edges has no bad vertex — the extremal version of the same proof.)

How to find it. "Too many neighbours of my colour" is a local count of monochromatic edges, and fixing one vertex changes only the edges at that vertex. When a local fix improves a global count, that count is the monovariant.

Step 1 — a move keeps the sum: $(x + y) + (-y) + (z + y) = x + y + z$. So $S > 0$ throughout.

Step 2 — the obvious candidates fail: the sum is invariant, and the sum of absolute values can go up. Try $f = \sum_{i=1}^5(x_i - x_{i+2})^2$ (indices mod $5$), which compares each vertex with the two vertices not adjacent to it.

Step 3 — label the pentagon $v, x, y, z, w$ and apply the move at $y$. Only the five terms involving $x$, $y$ or $z$ change, and a direct expansion gives $f_{\text{new}} - f_{\text{old}} = 2y(v + x + y + z + w) = 2yS$.

Step 4 — since $y < 0 < S$, every move lowers $f$ by at least $2$; $f$ is a nonnegative integer, so at most $\tfrac{f_0}{2}$ moves can be made. $\blacksquare$

How to find it. Look for a quadratic quantity: the move is linear, so a quadratic changes by a linear expression in $y$, and the only linear expression available with a known sign is $S$. Among the symmetric quadratics, try $\sum x_i^2$, $\sum(x_i - x_{i+1})^2$, $\sum(x_i - x_{i+2})^2$ in turn; the last one's change factors as $2yS$.

A symmetry is a bijection that preserves whatever the problem measures (probability, value of an integrand, legality of a move). If it maps the event $A$ onto the event $B$, then $P(A) = P(B)$; if $A$ and $B$ also partition everything, both are $\tfrac12$. In games, if the second position is always the mirror image of the first, every reply is legal whenever the move it copies was legal, so the mirroring player is never the one stuck. The work in a symmetry proof is checking that the map really is a bijection preserving the right thing, including the fixed points.

Step 1 — let $h_A, t_A$ and $h_B, t_B$ be the numbers of heads and tails. Since $h_A + t_A = h_B + t_B + 1$, it is impossible that both $h_A \le h_B$ and $t_A \le t_B$ (the sums would differ by at most $0$). So exactly one of "$A$ has more heads" and "$A$ has more tails" happens: if $h_A \le h_B$ then $t_A > t_B$, and if $h_A > h_B$ then $t_A = h_B + t_B + 1 - h_A \le t_B$.

Step 2 — swapping heads and tails on every coin is a probability-preserving bijection of outcomes that exchanges the two events.

Step 3 — two events of equal probability that partition the space: each has probability $\tfrac12$. The answer is $\tfrac12$ for every $n$.

How to find it. Small case $n = 0$: $A$ flips one coin, $B$ none, probability $\tfrac12$. The answer not depending on $n$ signals a symmetry; the extra coin is exactly what breaks ties, so the two events cover everything.

Step 1 — the first player wins: she puts her first coin exactly at the centre, and afterwards answers each coin of the opponent by a coin at its reflection through the centre.

Step 2 — the answer is always legal. Before the opponent's move the position is centrally symmetric (it holds the centre coin and mirror pairs). The opponent's coin $C$ is legal, so it lies on the table and overlaps nothing; its mirror image $C'$ lies on the table too. $C'$ overlaps no earlier coin, because such an overlap would mirror to an overlap of $C$ with an earlier coin. $C'$ does not overlap $C$ itself: two coins symmetric about the centre overlap only if each covers the centre, which is already taken.

Step 3 — so the first player always has a move, and since the table fills up after finitely many coins, the second player is the one who eventually cannot move. $\blacksquare$

How to find it. A game on a symmetric board suggests copying; the only obstacle is the fixed point of the symmetry (a move cannot be answered by itself), and the first player removes it by occupying the centre.

Step 1 — warm-up in the plane, three points on a circle. Choose three random diameters first, then an endpoint of each by a fair coin; this gives three independent uniform points. For fixed diameters, of the $2^3 = 8$ triangles exactly $2$ contain the centre (a triangle and its reflection), so the probability is $\tfrac28 = \tfrac14$.

Step 2 — in space, choose three random lines $\ell_1, \ell_2, \ell_3$ through the centre $O$ with unit direction vectors $u_1, u_2, u_3$, and an independent uniform point $P$; the points are $P$ and $\varepsilon_iu_i$ with independent fair signs $\varepsilon_i$. Almost surely $u_1, u_2, u_3$ are independent, so $-P = c_1u_1 + c_2u_2 + c_3u_3$ uniquely, with every $c_i \ne 0$ almost surely.

Step 3 — $O$ lies inside the tetrahedron $P, \varepsilon_1u_1, \varepsilon_2u_2, \varepsilon_3u_3$ iff $0 = \lambda_0P + \sum\lambda_i\varepsilon_iu_i$ with all $\lambda \ge 0$ and $\lambda_0 > 0$, i.e. $-P = \sum\tfrac{\lambda_i}{\lambda_0}\varepsilon_iu_i$; by uniqueness this means $\varepsilon_i$ has the sign of $c_i$ for each $i$. Exactly one of the $8$ sign choices does.

Step 4 — so the probability is $\tfrac18$.

How to find it. Small dimension first: on a segment, two random points of $[-1, 1]$ straddle $0$ with probability $\tfrac12$; on a circle $\tfrac14$. The pattern $2^{-d}$ and the coin-flip structure suggest choosing the lines first and the signs last, which turns a geometric probability into counting sign patterns.