Symmetry and invariants

Idea: Ask what cannot change

When there are too many orders of moves to simulate, look for a quantity no move can change.

• Each move: $a+b$ out, $a+b-1$ in
• So the sum on the board falls by $1$ per move
• The order of moves never matters

Example: Erase and replace

Write $1$ to $10$. Repeatedly erase $a$ and $b$ and write $a+b-1$. What is the last number?

1. Each move lowers the sum by $1$
2. Moves: $10-1=9$; the starting sum is $55$
3. Last number: $55-9=46$

Idea: Candidates to test first

Test each on a single move written with letters, not numbers.

• The sum, or the sum plus a known drift
• The parity of a sum or of a count
• A product after a shift such as $x+1$, or a remainder

Quick check: A rule with a product

On $1$, $2$, $3$, a move replaces $a$ and $b$ with $a+b+ab$. What number is left?

Formula: Pairing, the Gauss idea

$1+2+\cdots +n=\frac{n(n+1)}{2}$

Write the run forwards and backwards: every column has the same total. Terms times the average of the ends.

Common mistake: Last minus first

Counting the terms from $13$ to $27$ as $14$. That slip shifts the whole sum by the average.

Instead Count last minus first plus one: $27-13+1=15$ terms, sum $15\times 20=300$.

Example: Tokens of 3 colours

$10$ red, $13$ green, $18$ blue. A move turns $2$ tokens of different colours into the third colour. Which colour can all end in?

1. A move changes the counts by $-1$, $-1$, $+2$: gaps change by $0$ or $3$
2. Red minus green is $10-13=-3$, a multiple of $3$
3. Red minus blue $10-18=-8$, green minus blue $13-18=-5$: only all blue works

Idea: Symmetry wins games

Players take turns placing equal coins on a round table; whoever cannot place one loses.

• The first player takes the exact centre
• Then mirrors every move through the centre
• The mirror spot is always free, so the other player runs out first

Idea: Name the invariant first

Say "the sum drops by $1$ per move" or "the product of $x+1$ is fixed" before any arithmetic.

• Then give the starting value
• Then the number of moves
• That solves every version, not just this one