Problem 1 — The number that survives

Here is the problem we are going to solve today.

Write the numbers 1, 2, 3, …, 4n−1 on a board. In one move, rub out any two numbers and write down their difference instead. Prove that after 4n−2 moves, the single number left on the board is even.

Don't worry about the n yet. We'll get to it. Let's just play.

1. Let's actually play the game

Take n = 2. Then 4n − 1 = 7, so the board starts like this:

BOARD:  1  2  3  4  5  6  7

A move: pick any two of them, erase both, write their difference. (Difference means the bigger minus the smaller — we always write a non-negative number. More on that in a moment.)

Let me play a few moves.

1  2  3  4  5  6  7      pick 3 and 7  →  difference 4
1  2  4  5  6  4         pick 1 and 6  →  difference 5
2  4  5  4  5            pick 5 and 5  →  difference 0
2  4  4  0               pick 2 and 4  →  difference 2
4  0  2                  pick 4 and 0  →  difference 4
2  4                     pick 2 and 4  →  difference 2
2                        ← one number left

We started with 7 numbers and ended with 1. Notice the count: every move eats two numbers and produces one, so every move makes the board exactly one number shorter. From 7 numbers down to 1 is 6 moves. And 4n − 2 = 8 − 2 = 6. That part of the problem statement is just arithmetic — no cleverness needed.

The final number was 2. Even.

Now play it again, differently:

1  2  3  4  5  6  7      pick 1 and 2  →  1
1  3  4  5  6  7         pick 6 and 7  →  1
1  3  4  5  1            pick 3 and 4  →  1
1  5  1  1               pick 5 and 1  →  4
1  1  4                  pick 1 and 1  →  0
4  0                     pick 4 and 0  →  4
4

Final number: 4. Even again.

Try it yourself a few times. You will never get an odd number. That is what we have to prove.

2. Why the obvious approach dies

The obvious approach is: figure out what the final number is.

But you can't. We just got 2 once and 4 another time. The final number genuinely depends on how you play. And the number of possible ways to play is enormous — on the very first move alone you're choosing 2 numbers out of 7, which is 21 choices, and it multiplies from there. Checking every case is hopeless, and hopeless for a real reason: there is no single answer to find.

So we change the question.

We stop asking "what is the final number?" — which has no fixed answer — and start asking:

What is true about the board that stays true no matter what I do?

That question has an answer. Finding it is the entire chapter, and this problem is our first one.

A quantity that never changes, no matter which legal move you make, is called an invariant. If you can find an invariant, you get a superpower: whatever is true of it at the start is true of it at the end, and you never had to follow the middle at all.

Before we can hunt for one, we need two pieces of equipment. Let's build them properly.

3. Equipment 1: parity

Parity is a fancy word for one single fact about a whole number: whether it is even or odd. That's it. The parity of 7 is "odd". The parity of 12 is "even".

Here is the definition that actually gets used in proofs, and it's worth memorising in this form:

• m is even means: m = 2k for some whole number k. (12 is even because 12 = 2 × 6.)
• m is odd means: m = 2k + 1 for some whole number k. (7 is odd because 7 = 2 × 3 + 1.)

Note that 0 = 2 × 0, so zero is even. This trips people up. Zero is even.

Now, the rules of the game. What happens to parity under + and − ?

	result
even + even	even
even + odd	odd
odd + odd	even
even − even	even
even − odd	odd
odd − odd	even

Don't memorise the table — derive it once and you'll own it forever. Take the surprising row, odd + odd:

$$(2a+1) + (2b+1) = 2a + 2b + 2 = 2(a + b + 1)$$

The answer is 2 times a whole number, so it is even. Done. That's a complete proof, and it's three lines of class-8 algebra.

Try odd − odd yourself:

$$(2a+1) - (2b+1) = 2a - 2b = 2(a-b)$$

Even. Notice this is even even if a − b is negative — −6 is just as even as 6.

The one row that matters most for us:

Adding or subtracting an even number never changes parity.

7 + 4 = 11: odd stayed odd. 12 − 6 = 6: even stayed even. This is the sentence we're going to build the whole proof on, so sit with it for a second. Even numbers are invisible to parity.

4. Equipment 2: the difference |a − b|

The move says "replace them by their difference". If I pick 3 and 7, is the difference 4 or −4?

For this game we always mean the non-negative one: 4. There's a standard notation for it.

$$|a - b| \;=\; \text{the distance between } a \text{ and } b \text{ on the number line}$$

Those vertical bars are absolute value. |4| = 4 and |−4| = 4. The bars strip the minus sign off.

So |a − b| is "big minus small", written in a way that doesn't force you to say which is which:

• if a ≥ b, then |a − b| = a − b
• if b > a, then |a − b| = b − a

Two cases, and we will have to handle both. That's normal. Don't be scared of a proof that splits into cases — it's usually just bookkeeping.

5. Hunting the invariant

We have a board full of numbers. What quantities could we watch?

• How many numbers are on the board? That changes — it drops by 1 every move. Definitely not invariant. (Though it is useful, and we already used it: that's how we knew 4n − 2 moves get us to one number. A quantity that changes predictably in one direction is called a monovariant, and it will get its own tutorial later.)
• The biggest number on the board? Changes messily.
• The total of all the numbers on the board? Let's check.

Start: 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

Take the first playthrough above. After the move that replaced 3 and 7 by 4, the board was 1, 2, 4, 5, 6, 4 — totalling 22. So the total changed: 28 → 22. The total is not invariant.

But look at how it changed. It dropped by 6. An even amount.

The next move replaced 1 and 6 by 5, so the total went 22 → 20. Dropped by 2. Even again.

The next replaced 5 and 5 by 0, so 20 → 10. Dropped by 10. Even again.

Something is going on. The total isn't invariant — but its parity might be. 28, 22, 20, 10 — all even. Let's prove it.

The key calculation

Suppose the two numbers we pick are a and b. Before the move they contribute a + b to the total. After the move they contribute |a − b|. Every other number on the board is untouched.

So:

$$\text{change in total} = (a+b) - |a-b|$$

Now the two cases.

Case 1: a ≥ b. Then |a − b| = a − b, so

$$(a+b) - (a-b) = a + b - a + b = 2b$$

Case 2: b > a. Then |a − b| = b − a, so

$$(a+b) - (b-a) = a + b - b + a = 2a$$

In both cases the change is 2 × (a whole number) — that is, even.

If you want it in one line:

$$\text{the total always drops by } 2\times\min(a,b)$$

twice the smaller of the two. Check it against our moves: picking 3 and 7 dropped the total by 2 × 3 = 6. ✓ Picking 5 and 5 dropped it by 2 × 5 = 10. ✓

And from Section 3 we know: subtracting an even number never changes parity.

The invariant: the parity of the total of all numbers on the board never changes. If it starts even, it is even after every single move, forever, no matter how you play.

That's the whole idea of the chapter, and you've just met it. We couldn't predict the total. We didn't need to. We only needed one bit of information about it — even or odd — and that we could nail down completely.

6. Equipment 3: what does the total start at?

We need the starting total: 1 + 2 + 3 + … + (4n − 1).

Adding up that many numbers one at a time is not an option when n could be a million. We need the formula.

A short story

There's a famous school story about Carl Friedrich Gauss, in Germany around 1785. His teacher, wanting a quiet half hour, told the class to add up all the numbers from 1 to 100. Gauss, aged about seven, put his slate on the desk almost immediately with a single number on it: 5050.

The story may have grown in the telling, but the trick he used is real and it's beautiful.

The trick

Write the numbers from 1 to 100 forwards, and underneath, the same numbers backwards:

   1 +   2 +   3 + ... +  98 +  99 + 100
 100 +  99 +  98 + ... +   3 +   2 +   1
 ---------------------------------------
 101 + 101 + 101 + ... + 101 + 101 + 101

Every column adds to 101, and there are 100 columns. So the two rows together total 100 × 101 = 10100. But the two rows are the same sum written twice, so one row is half of that: 5050.

The same argument with m instead of 100: every column adds to m + 1, there are m columns, so

$$1 + 2 + 3 + \dots + m = \frac{m(m+1)}{2}$$

Sanity-check it on our board: m = 7 gives (7 × 8) ÷ 2 = 28. ✓ That's the total we computed by hand earlier.

Applying it

Our board starts at 1, 2, …, 4n − 1, so m = 4n − 1 and m + 1 = 4n:

$$\text{starting total} = \frac{(4n-1)(4n)}{2} = 2n(4n-1)$$

The 4n on top and the 2 underneath simplify, because 4n ÷ 2 = 2n. So the starting total is 2 × (a whole number).

The starting total is even. For any n at all.

(Check with n = 2: 2 × 2 × 7 = 28. ✓)

7. Putting it together

Now we just chain the three facts.

1. The board starts with 4n − 1 numbers, totalling 2n(4n − 1), which is even.
2. Every move changes the total by an even amount, so the total stays even — after 1 move, after 100 moves, after all 4n − 2 moves. It doesn't matter how the moves were chosen.
3. Every move shrinks the board by one number. Starting from 4n − 1 numbers, after 4n − 2 moves exactly one number is left.
4. When only one number is on the board, that number is the total of the board. (A one-item sum is just the item.)
5. The total is even. Therefore the last number is even. ∎

Read step 4 again, because it's the quiet hinge of the whole proof. The invariant is about the total, which is an abstract thing about the whole board — but at the very end the board collapses to a single number, and at that instant the abstract thing and the concrete thing become the same object. That's the move: you track something abstract precisely because at the finish line it turns into the thing you were asked about.

8. What just happened (the method, stated plainly)

Every problem in this chapter runs on the same four steps:

1. Look at one move. Just one, in general terms (a and b, not 3 and 7).
2. Find something that move doesn't change — or changes only in a controlled way (like "always by an even amount").
3. Compute that quantity at the start.
4. Compute what it would have to be at the goal. If they disagree, the goal is impossible. If they agree in the way you need, you've proved your result.

Here: the quantity was the parity of the total. At the start it was "even". At the end it had to still be "even", and at the end the total was the answer. Done.

The hard step is always step 2, and there is no formula for it. What there is, is a list of usual suspects that you'll build up over the next twenty problems: parities, sums, sums of squares, remainders, products, colourings. Today you own the first one.

9. Your turn

Warm-up. Play the game on 1, 2, 3, 4, 5 three times, choosing wildly different moves. Predict the parity of the final number before you play. (The total is (5 × 6) ÷ 2 = 15, which is odd — so what must every final number be?)

Exercise 1. The numbers 1, 2, …, 10 are on a board and the same game is played. Can the last number be 7? Can it be 6? Can it be 100? (Careful — parity answers two of these. The third needs a different thought: what's the largest the final number could possibly be?)

Exercise 2. Same game, but now the move is "replace a and b by a + b" instead of the difference. What's the invariant now? Is it still just the parity, or do you get something stronger?

Exercise 3 (the real test). Change the move to: replace a and b by a + b − 1. Start with 1, 2, …, 10. What single number are you left with, and why is it the same every time? (Hint: something is exactly invariant here, not just its parity. Look for a quantity that combines the total with how many numbers are on the board.)

Bring your answers and we'll do Problem 2 — where the invariant is hiding not in a sum, but in a sum of squares.