Invariants and Colouring: Olympiad Problems and Proofs

← All lessons · Germany’s selection routes

Three checks before the first move

Try these without revealing the answers. They check tools, not how clever you are.

1. If an odd integer increases by an even integer, is the result odd or even?
2. Five coins show heads. If two of those heads are flipped to tails, how many heads remain?
3. On a checkerboard, do two side-adjacent cells have the same colour?

Answers and a route if you need one

1. Odd: write the numbers as $2u+1$ and $2v$ for integers u and v; their sum is $2(u+v)+1$. 2. Three heads remain; the change is −2. 3. No. Moving one cell horizontally or vertically changes the checkerboard colour. If the first two felt uncertain, use the parity lesson before Example 1. If the third was unclear, draw two alternating rows and mark two side-adjacent cells before Example 2. No score is stored for this check.

One unchanging fact can control many moves

A state is the complete current arrangement: which coins show heads, which cells are covered, or which numbers are on a board. A legal move is one change allowed by the question. An invariant is a quantity or property that stays the same under every legal move.

The head count might change while its odd-or-even status remains fixed. A tiling may look different while the difference between two colour counts remains fixed. In a number game, the useful expression may be a product instead of a sum.

1. Name itDefine exactly what you will track.
2. Check a moveCover every allowed case.
3. CompareCalculate the starting and target values.

Why does checking one arbitrary move cover a long sequence? After the first move the invariant has its starting value. If it still has that value after any number of moves, the next legal move preserves it again. Repeating this reasoning covers every finite sequence. You do not need to list those sequences.

A crucial limit: different invariant values prove impossibility. Matching values do not by themselves prove possibility. To show a target can be reached, give a legal construction or a separate proof.

Worked example 1 · Flip two coins

Ten coins show three heads and seven tails. A move flips any two distinct coins. Can all ten coins show heads?

Choose what to track. The number of heads changes, but it changes only a little. Let H be its current value. If we flip two heads, H decreases by 2. Two tails increase it by 2. One head and one tail leave it unchanged. These three cases cover every pair.

Thus H stays odd because it starts at 3. The target has $H=10$, which is even. The target is impossible. The argument works for ten moves, a million moves or any other finite number.

Worked example 2 · Colour balance in a tiling

A 4 by 4 board is tiled by four T-shaped pieces. Each piece consists of three cells in a row with a fourth attached to the middle cell; right-angle rotations are allowed. On a checkerboard colouring, how many of the four pieces cover three dark cells and one light cell?

Rather than examine every possible tiling, count colours. The full board has eight dark and eight light cells. In a T, the middle cell meets each of the other three by a side. Its colour is therefore opposite to all three of those cells. Every piece covers either three dark cells and one light cell, or one dark and three light cells.

Let x be the number of pieces of the first type. The remaining $4-x$ pieces each cover one dark cell. Since every dark cell is covered exactly once, we have $3x+(4-x)=8$. Simplifying gives $2x+4=8$, hence $x=2$.

The pictured arrangement shows that a tiling exists. The count proves that every tiling has two pieces of each type. The unchanging whole-board colour balance controls the types of pieces, even when their positions change. This is a colouring argument; it need not be described as a move that preserves each individual tile’s colour count.

Worked example 3 · Discover a shifted product

Write 1, 2, 3, 4, 5 and 6 on a board. A move erases two current numbers a and b and writes $a+b+ab$ in their place. Continue until one number remains. Find it.

Adding all entries does not help: the replacement introduces the extra term ab. Look for an expression involving both a and b in a more useful way. Multiplying $(a+1)(b+1)$ gives $ab+a+b+1$, just one more than the replacement. Therefore

$(a+b+ab)+1=(a+1)(b+1)$.

Track the product of one more than every current entry. If the other shifted factors have product R, the old total is $R(a+1)(b+1)$; after merging it is $R((a+b+ab)+1)$. The displayed identity says these are equal. If no other entries remain, take $R=1$.

Initially the invariant is $2\times3\times4\times5\times6\times7=5040$. Every move reduces the number of entries by one, so after five moves one number z remains. Its shifted product is $z+1$. Thus $z+1=5040$, giving $z=5039$, regardless of the choices of pairs. All moves are defined for these nonnegative integers, so reaching a one-entry state presents no extra obstruction.

When the first invariant is too weak

Try these candidates in order: the ordinary sum; its parity; its remainder after division by a useful integer; separate counts in rows or columns; a product after a small algebraic change. Test each candidate against every move before using it in a proof.

For a square grid, two colours may not be enough. To study straight three-cell bars, label cell (r,c) by the remainder of $r+c$ on division by 3. Three consecutive cells in either direction receive all three labels. Any collection of such bars must therefore cover equal numbers of the three labels. This is the bridge to Problem 9.

Coordinates here are row first, column second. A cell labelled 0 has row-plus-column sum divisible by 3; 0 is a label, not an empty cell.

Mistakes to catch before calling it a proof

• A fact preserved in your first two experiments might fail for a different legal move. List the move cases.
• Do not claim that the number of heads is fixed when only its parity is fixed.
• Equal colour counts or matching parity do not construct a route to the target.
• A product invariant needs a reason for every unchanged factor as well as for the pair being replaced.
• Define whether rotations, zero entries or repeated moves are allowed. Here bars may rotate by a right angle, zero entries are allowed in number games, and a legal move may be repeated.

A six-question practice session

The session draws from nine objective questions below. Two consecutive independent correct answers raise the target level; a mistake brings an easier unused question where available. A hinted answer keeps the level steady. The interactive session offers the first hint; the complete paper set has two progressive hints for every problem.

The checker checks your selected conclusion, not your written reasoning. Keep a proof on paper and use the workshop rubric. Saving is optional and off by default; your answers and proof notes are not sent to Analytics.

Interactive practice loads here. You can also use the complete question set below.

All nine problems, with progressive hints

Try each problem before opening its choices. Problems 1–3 check the tools; 4–6 combine an invariant with a complete argument; 7–9 require a more selective invariant. These are independently written practice tasks using standard mathematical ideas, not reproduced national contest questions.

Foundation

1. A move flips exactly two distinct coins. Which quantity is unchanged by every move?

Optional answer choices

1. The number of heads
2. Whether the number of heads is odd or even
3. The number of tails
4. The face shown by a flipped coin

Hint 1

Separate the cases: two heads, two tails, or one of each.

Hint 2

The head count changes by −2, 2 or 0. What do these changes share?

Answer and complete solution

Whether the number of heads is odd or even

Two heads become tails, decreasing the head count by 2. Two tails become heads, increasing it by 2. One head and one tail merely exchange roles, changing it by 0. Each change is even, so the parity of the head count stays the same.

Watch out: An invariant need not be the whole number. Its parity can stay fixed while the number changes.

Foundation

2. Start with the integer 4. A move replaces the current integer x by $3x+2$. Can the value ever become odd?

Optional answer choices

1. Yes, because the multiplier 3 is odd
2. Yes, after two moves
3. No: an even input always gives an even output
4. No: the value always stays 4

Hint 1

Write a general even current value as $x=2k$.

Hint 2

Substitute 2k into $3x+2$ and factor out 2.

Answer and complete solution

No: an even input always gives an even output

The initial value 4 is even. If a current value is $x=2k$ for an integer k, then the next value is $3(2k)+2=2(3k+1)$, which is even again. This argument applies at every step, so an odd value is impossible. The value does change: the first move gives 14. It is the parity, not the value itself, that is invariant.

Watch out: An odd multiplier times an even integer is even. Check the entire expression, including its added term.

Foundation

3. A 4 by 7 board has checkerboard colouring. Remove one domino at a time, always covering two side-adjacent cells. What is the number of uncovered dark cells minus uncovered light cells after any such removals?

Optional answer choices

1. −1
2. 0
3. 1
4. 2

Hint 1

First count the two colours on the full board.

Hint 2

Every domino removes one cell of each colour.

Answer and complete solution

0

Pair the four rows into two pairs. In each pair of rows, every column contains one dark and one light cell, so the board starts with 14 of each. A horizontal or vertical domino covers one of each colour. Removing it reduces both counts by 1, leaving their difference unchanged at 0.

Watch out: Cells meeting only at a corner are not side-adjacent and cannot form one domino.

Core

4. Twelve coins show five heads and seven tails. A move flips any two distinct coins. What is the fewest moves needed to reach exactly nine heads?

Optional answer choices

1. 1
2. 2
3. 3
4. It is impossible

Hint 1

How much can one move increase the head count?

Hint 2

Give both a lower bound and a sequence attaining it.

Answer and complete solution

2

The required increase is $9-5=4$. A move increases the head count by at most 2, so at least two moves are needed. Choose four of the seven tails and split them into two pairs. Flip one pair in each move. This creates four heads, reaching exactly nine in two moves. The lower bound is attained.

Watch out: Matching parity only says that this invariant gives no obstruction. A construction is still needed to prove possibility.

Core

5. A robot starts at (0,0). Its only moves are $(x,y)\longmapsto(x+2,y+1)$ and $(x,y)\longmapsto(x-1,y+1)$. Which target is impossible?

Optional answer choices

1. (4,2)
2. (1,2)
3. (0,3)
4. (1,1)

Hint 1

Compute the change in $x+y$ for each of the two moves.

Hint 2

The changes are 3 and 0. Starting at 0, the sum always remains divisible by 3.

Answer and complete solution

(1,1)

The first move adds 3 to $x+y$; the second adds 0. Thus $x+y$ is always divisible by 3. The target (1,1) has sum 2, so it is impossible. For completeness, denote the first move by A and the second by B. AA reaches (4,2), AB reaches (1,2), and ABB reaches (0,3). Those constructions verify the other choices.

Watch out: Check every permitted move. An expression preserved by just one of the two moves is not enough.

Core

6. Write 1, 2, 3, 4 and 5 on a board. Repeatedly erase any two current numbers a and b and replace them by $\lvert a-b\rvert$ (the nonnegative difference between them), until one number remains. What must be true of that final number?

Optional answer choices

1. It is odd
2. It is prime
3. It is divisible by 3
4. It is greater than 5

Hint 1

The sum changes, but perhaps its parity does not.

Hint 2

If $a\ge b$, the sum falls by $2b$; if $b\ge a$, it falls by $2a$.

Answer and complete solution

It is odd

If $a\ge b$, replacing $a+b$ by $a-b$ decreases the current sum by $2b$. If $b\ge a$, the decrease is $2a$. All current numbers are nonnegative integers, and in both cases the change is even. The initial sum is 15, so every later sum is odd. With one number left, that number equals the sum and is odd. The other choices need not hold: merge 4 and 5 to get 1, leaving 1,2,3,1; merge 3 and one 1 to get 2, leaving 1,2,2; merge the two 2s to get 0, then merge 1 and 0 to finish at 1. This is neither prime nor divisible by 3 nor greater than 5.

Watch out: A new zero is allowed even though the starting numbers are positive. The parity proof still works.

Stretch

7. On an initially white 5 by 5 board, a move flips the colours of all four cells of any side-aligned 2 by 2 block. Can only cells (1,1) and (1,2) become black?

Optional answer choices

1. No: two columns would have an odd number of black cells
2. Yes: the total number of black cells would be even
3. No: row 1 would have an odd number of black cells
4. Yes: flip the top-left block twice

Hint 1

The total number of black cells does not settle this target. Try a count in each individual column.

Hint 2

A block touches either zero or two cells in a given column. Track that column’s black-count parity.

Answer and complete solution

No: two columns would have an odd number of black cells

Each move flips two cells in each of two columns and no cells in the other columns. In any touched column, its black count changes by −2, 0 or 2, so its parity is preserved. Every column starts with zero black cells. The target has one black cell in column 1 and one in column 2, making those column counts odd. It is impossible. Row 1 would have two black cells, so its parity alone would not rule the target out.

Watch out: An even total is a necessary condition, but it is weaker than the separate parity condition in every column.

Stretch

8. Start with 0, 2, k and k, where k is a nonnegative integer. At each move replace any two current numbers a and b by $a+b+ab$. After three moves the final number is 74. What is k?

Optional answer choices

1. 3
2. 4
3. 5
4. No nonnegative integer works

Hint 1

Work backwards from the final shifted value, 75.

Hint 2

The preserved product starts at $3(k+1)^2$. Set it equal to 75.

Answer and complete solution

4

The identity $(a+b+ab)+1=(a+1)(b+1)$ preserves the product of one more than every current entry. At the start that product is $1\times3\times(k+1)\times(k+1)=3(k+1)^2$. At the end it is $74+1=75$. Hence $(k+1)^2=25$. Since k is nonnegative, $k+1$ is positive, so $k+1=5$ and $k=4$. Conversely, $k=4$ gives the preserved product 75, so every order of three merges ends at 74. This checks that the required value really works.

Watch out: Recover the starting parameter from the invariant. Keep the nonnegative-integer condition when taking the square root.

Stretch

9. Remove cells (1,1), (2,3) and (4,4) from a 6 by 6 board. Can the remaining board be tiled by straight 1 by 3 bars, placed horizontally or vertically, without overlaps?

Optional answer choices

1. Yes, because 33 is divisible by 3
2. No, because 33 is not divisible by 3
3. No: a three-colour count is unbalanced
4. Yes, because the removed cells are distinct

Hint 1

A two-colour checkerboard is not the only useful colouring. Label cell (r,c) by the remainder of $r+c$ on division by 3.

Hint 2

Each allowed bar covers one cell of each label. Count which labels were removed.

Answer and complete solution

No: a three-colour count is unbalanced

Label a cell by $r+c$ modulo 3. Along any three consecutive horizontal or vertical cells the labels are 0, 1 and 2 in some order, so every bar uses one of each. Each row of the full board has two of each label, giving 12 of each overall. The removed cells have sums 2, 5 and 8, all with remainder 2. The remaining counts are 12, 12 and 9. Eleven bars would require 11 of each label, which is impossible.

Watch out: A divisible area is necessary for tiling, but does not prove that the shapes can fit.

Proof workshop · Necessary is not sufficient

The following proofs are self-reviewed; no automatic score is assigned to arbitrary written answers. For each, check four things: the tracked property is defined, every legal move is covered, the starting/target comparison is correct, and the requested conclusion or construction is justified.

Proof A · Exactly which coin patterns are reachable?

There are n labelled coins, where n is an integer at least 2. A move flips any two distinct coins. Prove that one specified arrangement can be changed into another if and only if their head counts have the same parity.

Hint 1

One direction is the coin invariant. For the converse, mark only coins whose current face differs from their target face.

Hint 2

Let u coins need to change from heads to tails and v from tails to heads. Compare $v-u$ with $u+v$.

Complete proof and rubric

Necessity. Flipping two coins changes the head count by −2, 0 or 2, so any reachable arrangement has the same head-count parity.

Sufficiency. Suppose the head counts have the same parity. Let u count the coins currently heads that should be tails, and v those currently tails that should be heads. The target head count minus the current one is $v-u$, an even number. The number of mismatched coins is $u+v=(v-u)+2u$, also even.

Pair the mismatched coins arbitrarily, and flip each pair once. Both coins in a pair become correct; coins outside the pair are untouched. Every mismatched coin is included in exactly one pair, so the final arrangement is the desired one. If no coins mismatch, zero moves suffice.

Check your proof: Did you prove both directions? Did you show the mismatch count is even instead of assuming it? Did you explain why the pairing is a legal construction and include an already-correct arrangement?

Proof B · The fewest moves to four corners

Start with an all-white 5 by 5 board. A move flips all four cells of any side-aligned 2 by 2 block. What is the least number of moves needed to make precisely the four corner cells black?

Find a construction and prove that no shorter sequence works. There are 16 possible blocks, identified by their top-left cells in rows 1–4 and columns 1–4.

Hint 1

Try flipping each of the 16 blocks once. Count how often a corner, a noncorner edge cell and an interior cell are flipped.

Hint 2

For a lower bound, look at a rectangle consisting of rows 1 through i and columns 1 through j, where i and j are between 1 and 4. Which block moves flip an odd number of cells inside it?

Complete proof and rubric

A construction in 16 moves. Flip each possible block once. A corner cell belongs to one block, so it becomes black. A noncorner edge cell belongs to two blocks, so two flips restore it to white. An interior cell belongs to four blocks, so it also returns to white. Thus these 16 moves give exactly the target.

A tool for the lower bound. A prefix rectangle here means all cells in rows 1 through i and columns 1 through j. It always starts at the board’s top-left corner. Fix any i and j from 1 through 4. It initially has zero black cells. In the target it contains only the top-left black corner, so its black count must become odd.

A 2 by 2 block meets such a rectangle in 0, 1, 2 or 4 cells. Flipping an even number of cells preserves its black-count parity. For the overlap to contain exactly one cell, exactly one of the block’s two rows must lie inside the rectangle, so the block’s top row must be row i. Likewise, its left column must be column j. Thus only the block with top-left cell (i,j) changes the black-count parity of this particular prefix rectangle.

That block must therefore be used an odd number of times, in particular at least once. There are 16 choices of (i,j), and each requires its own block at least once. Every move uses just one block, so at least 16 moves are required. Our construction attains this bound. The minimum is 16.

Check your proof: Did you verify the construction on corners, edges and interior cells? Did you define each prefix rectangle? Did you explain why only one block changes its parity? Did you prove a lower bound as well as produce a sequence?

Choose the next useful step

If choosing an invariant was difficult, take one example and make a table showing its value before and after each kind of move. If you can find an obstruction but struggle to prove possibility, write out the construction in Your turn 1 or Proof A. If the objective questions felt comfortable, write Proof B without revealing the solution.

For German preparation, move from this lesson to the school-round practice, then the regional proof papers. The Germany guide explains the separate MO and Bundeswettbewerb routes and the later shared selection process.

Prepared for IMOolympiad.com. Original exposition and practice based on standard invariant and colouring techniques; no official problem reproduction or endorsement is claimed. The national MO overview and official released-paper archive provide the contest context. Consult the organiser and your invitation for current arrangements. Report an unclear step or correction.