Odd and Even Numbers

In one sentence

Parity is just the remainder mod $2$ : the coarsest sieve there is, sorting the integers into only two classes. It is used in almost the same way every time:

Find a quantity whose parity never changes, whatever you do (or changes at every step). If the start and the goal have different parities, the goal can never be reached.

All you need to know is three facts:

odd ± odd = even, even ± even = even, odd ± even = odd; so adding a number and subtracting the same number have the same effect on parity.
When you add up a bunch of numbers, the parity of the sum depends only on how many of them are odd.
A product is odd $⟺$ every factor is odd.

Why ±1 ±2 ±3 ±4 ±5 ±6 can never make 0

Step 1 / 5

All plus signs
$1 + 2 + 3 + 4 + 5 + 6 = 21$ , which is odd.

$1 + 2 + 3 + 4 + 5 + 6 = 21$
Change one sign
Change two more
Grab what never changes
When parity lets you through

Stop 1 · Operations: flipping cups

Predict first

$7$ cups stand facing up. Each move you must flip exactly $4$ of them. Can you, after some number of moves, get all $7$ cups facing down?

YesNo

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

Stop 2 · Boards: black-and-white coloring

Color the cells of the board black and white according to the parity of “row number + column number”. Two neighboring cells are always one black and one white. The coloring is parity drawn onto the picture.

8 \times 8

board with two opposite corners removed leaves

62

cells. Can

31

dominoes of size

1 \times 2

cover it? Then try removing other cells.

The two opposite corners you removed have the same color. That leaves $30$ cells of one color and $32$ of the other, but every domino covers one black and one white cell, so $31$ dominoes need $31$ black and $31$ white. The board cannot be covered, and you don't even need to try.

Stop 3 · Equations: two ways

One problem, several solutions

Prove that $x^{2} - y^{2} = 2022$ has no integer solutions.

Parity argument

$x^{2} - y^{2} = (x - y) (x + y)$ . Since $(x + y) - (x - y) = 2 y$ is even, $x - y$ and $x + y$ have the same parity.

Both odd: the product is odd, so it is not $2022$ .
Both even: the product is a multiple of $4$ . But $2022 = 4 \times 505 + 2$ is not a multiple of $4$ .

Neither case works, so there are no integer solutions.

CostNo tools needed, but you have to think of factoring it as (x−y)(x+y).

Mod 4

A square divided by $4$ can only leave $0$ or $1$ (the topic of the next stop). So $x^{2} - y^{2}$ divided by $4$ can only leave $0, 1, 3$ , while $2022$ leaves $2$ .

CostOne step, but you need to know first that squares leave only 0 or 1 mod 4.

The two solutions say the same thing: mod $4$ simply splits “odd and even” one level finer. When a parity argument is not enough, the next step is to switch to a better modulus.

Practice

Exercise 1Basic

Is $1 + 2 + 3 + \dots + 50$ odd or even? (Don't work out the sum.)

Exercise 2Basic

Put a $+$ or a $-$ in front of each of $1, 2, 3, \dots, 10$ however you like, then work out the result. What is the smallest non-negative result you can get?

Exercise 3Advanced

$a_{1}, a_{2}, \dots, a_{9}$ is any arrangement of $1, 2, \dots, 9$ . Prove that the product $(a_{1} - 1) (a_{2} - 2) \dots (a_{9} - 9)$ is always even.

Exercise 4Challenge

A $5 \times 5$ grid has one beetle in each cell. When a whistle blows, every beetle crawls to a neighboring cell that shares a side with its own. Prove that after the whistle some cell must be empty.

In one sentence

Why ±1 ±2 ±3 ±4 ±5 ±6 can never make 0

Stop 1 · Operations: flipping cups

Stop 2 · Boards: black-and-white coloring

Stop 3 · Equations: two ways

Parity argument

Mod 4

Practice

Mistake Museum · Exhibits from this stop

Parity matches, so it must be possible

Thinking a sum and a difference can have different parities