# Invariants and parity

Puzzles and Brainteasers, lesson 2. Free.

URL: https://insideout.sh/courses/puzzles/02
Updated: 2026-11-12T09:52:14Z
Prove a goal is impossible by finding what never changes.

Some puzzles ask whether a goal can be reached at all. Trying moves until you give up proves nothing, since the next try might work. This lesson shows how to prove a goal is out of reach, and a plan that puts the same idea to work. You only need to know odd from even.

By the end, you can:
1. Prove a goal is impossible by finding a quantity that no move can change.
2. Rule out a tiling by colouring the board so each piece covers a fixed mix of colours.
3. Share the parity of a hidden count so each person can work out the one piece they can't see.

## Part 1. What never changes

**Guess first:** The numbers 1 to 10 are on a board. A move wipes out any two numbers and writes their difference, bigger minus smaller. After 9 moves one number is left. What can it be?
A. Any odd number from 1 to 9
B. Any number from 0 to 10
C. Any even number
D. Always 1
Answer: A. It's always odd, and each of 1, 3, 5, 7 and 9 can happen. The example shows why it can never be even, without playing a single game.

You could play a hundred games, get an odd number every time, and still not know that the next game can't end on 0. To rule a result out, look for something that every move leaves alone.

**Example 1.1: The difference game**
Problem: Show that the last number on the board can never be even.
1. Look at what a move does: a, b → a − b (Call the two numbers a and b, with a the bigger. Two numbers go and one comes back, so the count, the largest number and the total can all change.)
2. Watch the total: (a − b) − (a + b) = −2b (The total drops by twice the smaller number, which is always an even amount.)
3. Keep only odd or even: 1 + 2 + … + 10 = 55, odd (Taking away an even amount never turns an odd total even. So the total is odd after every move.)
4. Read the end: last number = total, odd (When one number is left, it is the total.)
Answer: The last number is always odd.

The total itself changes with every move, so it's no use on its own. What survives is whether it's odd or even. Finding the part that survives is the skill this lesson teaches.

**Invariant and parity**: An **invariant** is a quantity that no move can change. **Parity** is whether a whole number is odd or even. If the start and the goal differ in an invariant, no run of moves can get from one to the other.

The trap is building on a quantity that does change. The total, the largest number and the count of numbers all move. Test any candidate on one move before you trust it.

**Your turn:** A jar holds 9 white and 6 black counters, with spare black ones outside. Take out two. If they match, put one black back. If they differ, put one white back. Repeat until one counter is left. What colour is it?
A. White, always
B. Black, always
C. It depends on the order you draw
D. Either, with equal chance
Answer: A. Watch the whites. A move takes out two whites or none, since a mixed pair puts its white back. So the number of whites changes by 0 or 2 and stays odd. It starts at 9, can never reach 0, and the last counter is white.

## Part 2. Colour the board

**Guess first:** Take an 8 by 8 grid of squares and remove two opposite corners, leaving 62. A domino covers two squares side by side. Can 31 dominoes cover the 62 squares exactly, with no overlap?
A. There's no way to know without trying every layout
B. Only if some dominoes lie diagonally
C. Yes
D. No
Answer: D. No. Colour the grid like a chessboard: the two corners removed share a colour, which leaves 30 of one colour and 32 of the other, and every domino covers one of each. No search of layouts is needed.

Counting squares doesn't settle it, because 62 is even and 31 dominoes is the right number. You need a finer count.

**Example 2.1: The grid with two corners gone**
Problem: Show that no layout of 31 dominoes covers the 62 squares.
1. Colour it: dark, light, dark, light, … (Colour the squares like a chessboard, so every square's neighbours are the other colour.)
2. See what a domino covers: 1 dark + 1 light (Its two squares sit side by side, so they differ in colour, wherever it goes.)
3. Count the colours left: 30 dark, 32 light (Opposite corners are the same colour, here dark. Removing both takes two from the 32 dark squares.)
4. Compare: 31 dominoes need 31 + 31 (Any 31 dominoes cover exactly 31 dark squares, and only 30 are left.)
Answer: No layout works.

Figure 1: Opposite corners share a colour, so 30 dark and 32 light squares are left. Every domino, wherever it lies, covers one of each.

The argument never looks at a single layout. It shows that every layout fails at once, which is why it's a proof and a search isn't.

**Colouring argument**: Colour the board so every piece covers the same mix of colours wherever it sits. If the board's colour counts can't match what the pieces cover, no tiling exists.

A colouring can only prove "no". Remove one dark and one light square instead, and the counts match, 31 and 31. That rules nothing out, but it doesn't prove a tiling exists either. You still have to find one.

**Your turn:** A 5 by 5 grid loses one square: the one beside a corner square. Can 12 dominoes cover the 24 squares left?
A. There's no way to know without trying layouts
B. Yes, since 24 is even
C. Yes, in exactly one way
D. No
Answer: D. Colour it like a chessboard with dark corners: 13 dark, 12 light. The square beside a corner is light, so 13 dark and 11 light are left, and 12 dominoes need 12 of each. An even number of squares is needed, but it isn't enough.

## Part 3. Parity as a plan

**Guess first:** Ten people stand in a line facing the front. Each wears a red or blue hat and sees every hat ahead, but not their own or any behind. From the back, each says one word, "red" or "blue", heard by all. They agree a plan beforehand. How many can be sure of naming their own hat?
A. 5
B. None, each is a coin flip
C. 10
D. 9
Answer: D. 9: everyone except the person at the back. One word from the back is enough: whether the red hats ahead of it are odd or even in number.

Nobody sees the back person's hat, so their word can't be sure of it. But it can carry one fact that everyone in front needs. The question is which fact.

**Example 3.1: Five hats in a line**
Problem: Five people use the plan. From the back the hats are unknown, red, blue, red, red. The back person says "red" if they see an odd number of red hats, "blue" if even. Follow each person.
1. The back person: sees 3 reds, odd → "red" (The word describes the hats ahead, so it matches their own hat only half the time.)
2. Person 2: sees 2 reds, even → "red" (The reds from person 2 forward are odd, and they see an even number, so the missing red is their own.)
3. Person 3: 1 named + 2 seen = 3, odd → "blue" (Reds named since the back person spoke, plus reds seen, is already odd, so their own hat is blue.)
4. Persons 4 and 5: 1 + 1 = 2 → "red"; 2 + 0 = 2 → "red" (The same sum each time, reds named plus reds seen: even means their own hat is red, odd means blue.)
Answer: Everyone but the back person names their hat for certain.

Figure 2: The five-hat line. Each person adds the reds named behind them to the reds they see. Since the back person's word said odd, an even sum means their own hat is red.

**Parity bit**: One extra bit that says whether a count is odd or even. If you know a group's parity and can see every member but one, the missing one is fixed.

The tempting plan works in pairs: the back person names the next hat, and its owner repeats it. Only half are then sure. The parity word beats it because it speaks to everyone at once.

**Your turn:** Five people use the same plan. The back person says "red", so they see an odd number of reds. Person 2 sees 2 reds ahead. Person 3 sees 1 red ahead. What do persons 2 and 3 say?
A. Red, then red
B. Blue, then red
C. Red, then blue
D. Blue, then blue
Answer: A. Person 2 sees an even number of reds but was told odd, so their own is red. Person 3 heard 1 red named and sees 1, an even 2, so their own is red too. Blue for person 3 forgets the red named behind them.

## Where you'll meet it

> **In interviews**: When a puzzle asks whether something can be done, it often wants an invariant. Say the quantity you're testing, and check it on one move out loud. Parity comes up with flips, swaps and pairings, colourings with grids and tiles. Prove "no" with the invariant, and prove "yes" by showing one way.

> **On the job**: Disk arrays use the hat trick. RAID 5 stores a parity block beside each group of data blocks: every bit of it records whether the matching bits of the others hold an odd or even number of 1s. When one disk fails, each lost bit is the one value that makes the parity come out right, so the array rebuilds it.

```python
from itertools import product

def endings(nums):                     # every last number the game can reach
    seen, ends, todo = set(), set(), [tuple(nums)]
    while todo:
        s = todo.pop()
        if s in seen:
            continue
        seen.add(s)
        if len(s) == 1:
            ends.add(s[0])
        for i in range(len(s)):
            for j in range(i + 1, len(s)):
                rest = s[:i] + s[i + 1:j] + s[j + 1:]
                todo.append(tuple(sorted(rest + (s[j] - s[i],))))
    return sorted(ends)

print(endings(range(1, 11)))           # [1, 3, 5, 7, 9]

def sure(hats):                        # hats[0] is the back; 1 means red
    said = [sum(hats[1:]) % 2]         # the back person's parity word
    for i in range(1, len(hats)):
        said.append((said[0] - sum(said[1:]) - sum(hats[i + 1:])) % 2)
    return sum(s == h for s, h in zip(said, hats))

print(min(sure(h) for h in product((0, 1), repeat=10)))  # 9
```

The first search plays every possible game, over 7,000 board states, and never ends on an even number. The second tries all 1,024 lines of hats, and at least 9 people are right in every one.

## Check yourself

**Question 1.** Seven coins lie heads up. A move turns over any two of them. Can you get all seven tails up?
A. No: the number of heads stays odd
B. Yes, in 4 moves
C. Yes, if you turn neighbours
D. No: the number of heads never changes
Answer: A. Each move changes the number of heads by −2, 0 or +2, so it stays odd: 7, 5, 3, 1, never 0. The number of heads itself does change, so it can't be the invariant. Its parity is.

**Question 2.** A 4 by 4 grid loses the two end squares of its top row, leaving 14. Can 7 dominoes cover them?
A. No: the colours don't match
B. Yes
C. No: two squares are missing
D. Only with a domino on a diagonal
Answer: B. The two end squares are different colours, so 7 dark and 7 light are left, and the colouring rules nothing out. Then find a layout: one domino fills the middle of the top row, and the full 3 by 4 block below takes six more.

**Question 3.** In the line of 10 using the parity plan, with hats given at random, what's the chance all 10 are right?
A. 9/10
B. 1/2
C. 1
D. 1/1,024
Answer: B. The 9 in front are always right. Only the back person speaks without knowing, and their word matches their own hat half the time. The answer 1/1,024 is ten blind guesses in a row.

**Question 4.** Now hats come in red, blue and green, and each person says one colour. How many of the 10 can be sure of naming their own hat?
A. 3
B. 0
C. 9
D. 6
Answer: C. Number the colours 0, 1 and 2. The back person names the colour whose number is the remainder when the total of the hats ahead is divided by 3. Everyone in front knows every other hat in that total, so only one colour of theirs gives the right remainder. Still 9.

## What to remember

1. An invariant is a quantity no move can change: on the board of 1 to 10 the total starts at 55, odd, and each move takes off an even amount, so the last number is odd.
2. Test a candidate on one move first. The total and the count of numbers both change; only the total's parity survives.
3. Colour the board so every piece covers a fixed mix: a domino covers one dark and one light, and the 8 by 8 grid without opposite corners has 30 and 32.
4. A colouring proves only "no". When the colour counts match, you still have to find a tiling.
5. One parity word from the back of a line of 10 lets the other 9 name their hats for certain.

Next: Next, a counting idea that proves something must happen: put more items than boxes, and some box holds two.
