Parity

In one sentence

Integers come in two kinds, odd and even. The properties used most often:

$a + b$ and $a - b$ have the same parity;
a sum of an odd number of odd numbers is odd, and a sum of an even number of odd numbers is even;
a product of integers is odd if and only if every factor is odd.

The power of a parity argument: it keeps just one piece of information, the value “mod $2$ ”, and that is often exactly the part of the problem that does not change.

Predict first

The board shows $1, 2, \dots, 10$ . Each move erases any two numbers $a, b$ and writes $∣ a - b ∣$ . After $9$ moves one number is left. Can that number be $0$ ?

YesNo

Choose an answer first; then you can see the result.

Example: erase two of 1 to 10, write the difference; the last number is odd

Step 1 / 4

Find a quantity
Each move touches only two numbers, so look at the sum of all the numbers, $S$ . At the start $S = 1 + 2 + \dots + 10 = 55$ .

$S_{0} = 55$
The sum changes, its parity does not
A parity invariant
Conclusion

Stop 1 · The Principle of Classification (Vol. 1)

Sort the integers into two classes by parity, and the problem becomes one about how the two classes are arranged.

Example: can 1, 2, …, n be arranged in a circle so that every two neighbors have an odd sum?

Step 1 / 4

What an odd sum means
A sum of two numbers is odd $⟺$ one is odd and one is even. So odd and even numbers must alternate around the circle.

$a + b odd ⟺ a \neq \equiv b (mod 2)$
An alternating circle
n odd: impossible
n even: possible

Stop 2 · Periodic Sequences (Vol. 5)

The sequence itself keeps growing, but its parity has only two states, and it is often periodic.

Example: a₁ = a₂ = 1, aₙ₊₂ = aₙ₊₁·aₙ + 1. Is a₁₀₀ odd or even?

Step 1 / 4

Track only the parity
odd × odd + 1 = even, odd × even + 1 = odd, even × odd + 1 = odd.

$1, 1, 0, 1, 1, 0, \dots (mod 2)$
Check a few terms
Period 3
Conclusion

Stop 3 · The Fibonacci Sequence (Vol. 5)

One problem, several solutions

The Fibonacci sequence: $F_{1} = F_{2} = 1$ , $F_{n + 2} = F_{n + 1} + F_{n}$ . Prove that $F_{n}$ is even if and only if $3 ∣ n$ .

The parity is periodic

Mod $2$ : $1, 1, 0, 1, 1, 0, \dots$ . Each term is decided by the two before it, and $(F_{4}, F_{5}) \equiv (1, 1) \equiv (F_{1}, F_{2})$ , so the shadow has period $3$ .

So $F_{n} \equiv 0 (mod 2) ⟺ n \equiv 0 (mod 3)$ .

CostThe most direct: squash the sequence down to its mod 2 “shadow”.

Induction with step 3

$F_{n + 3} = F_{n + 2} + F_{n + 1} = 2 F_{n + 1} + F_{n}$ , so $F_{n + 3} \equiv F_{n} (mod 2)$ .

Check that $F_{1}, F_{2}$ are odd and $F_{3} = 2$ is even, then use induction with step size $3$ : three chains cover $n \equiv 1, 2, 0 (mod 3)$ .

CostNo mention of periods, just induction; first stretch the recurrence over three steps.

Practice

Exercise 1Basic

The board shows $1, 2, \dots, 2025$ . Each move erases two numbers and writes the absolute value of their difference. What remainder does the last number leave when divided by $2$ ?

Exercise 2Basic

How many of the first $100$ Fibonacci numbers $F_{1}, F_{2}, \dots, F_{100}$ are even?

Exercise 3Advanced

$P (x)$ is a polynomial with integer coefficients, and $P (0)$ and $P (1)$ are both odd. Prove that $P (x)$ has no integer root.

Exercise 4Challenge

Each of $a_{1}, a_{2}, \dots, a_{n}$ is $1$ or $- 1$ , and $a_{1} a_{2} + a_{2} a_{3} + \dots + a_{n - 1} a_{n} + a_{n} a_{1} = 0$ . What is the smallest positive integer $n$ for which this is possible?

In one sentence

Example: erase two of 1 to 10, write the difference; the last number is odd

Stop 1 · The Principle of Classification (Vol. 1)

Example: can 1, 2, …, n be arranged in a circle so that every two neighbors have an odd sum?

Stop 2 · Periodic Sequences (Vol. 5)

Example: a₁ = a₂ = 1, aₙ₊₂ = aₙ₊₁·aₙ + 1. Is a₁₀₀ odd or even?

Stop 3 · The Fibonacci Sequence (Vol. 5)

The parity is periodic

Induction with step 3

Practice

Mistake Museum · Exhibits from this stop

The sum is even, so both must be even

The parity matches, so it can be done

Stops on this line