Coloring

In one sentence

A coloring is a classification: sort the objects into a few classes, chosen cleverly so that every tile, every move or every structure touches a fixed number of objects of each class.

each 1 \times 4 strip = A + B + C + D (colored by (r + c) mod 4)

A question about the endlessly many ways of “placing things” then becomes a single count: count how many cells each color has, and you know which things can never be done. Coloring is also often used to prove that something “must exist”: however you split into two classes, one class hides some structure.

Predict first

Can a 10×10 board be covered exactly by $25$ strips of size 1×4?

Yes:

100 = 25 \times 4

NoIt depends where you start

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

Example: a 10×10 board and 1×4 strips

Step 1 / 4

Just try to tile it
Lay two strips across each row, filling the first $8$ columns; in the two right-hand columns, lay two strips down each. That is $24$ strips, and a 2×2 square is left in the bottom-right corner, where no 1×4 strip fits.

$20 + 4 = 24 strips, 4 cells left$
Four-color diagonals
Count the colors
Contradiction

The last step puts the $24$ strips back: the four uncovered cells are exactly A $1$ , B $2$ , C $1$ , D $0$ , which is $25, 26, 25, 24$ minus $24$ each.

Stop 1 · Partitions of a set (Vol. 1)

Splitting ${1, 2, \dots, n}$ into two classes is the same as coloring each number with one of two colors. The question “does one class always contain $x, y, x + y$ ?” is a search for a monochromatic structure.

Tap the numbers to change their colors. For

n = 4

, can you avoid a monochromatic

x + y = z

? What about

n = 5

Example: however {1, 2, 3, 4, 5} is split into two classes, one class contains x, y, x + y (x = y allowed)

Step 1 / 4

Say 1 is red
Suppose it can be avoided. $1 + 1 = 2$ , so $2$ must be blue.

$1 \in R \Rightarrow 2 \in B$
Colors that are forced
5 has nowhere to go
But 4 numbers can do it

Stop 2 · The principle of classification: coloring lattice points by parity (Vol. 1)

Color each lattice point $(x, y)$ with one of four colors according to $(x mod 2, y mod 2)$ . The midpoint $(\frac{x _{1} + x _{2}}{2}, \frac{y _{1} + y _{2}}{2})$ of two points of the same color is again a lattice point.

Example: among any 5 lattice points in the plane, two have a midpoint that is also a lattice point

Step 1 / 3

Four colors
Classify by the parity of the coordinates: (even, even), (even, odd), (odd, even), (odd, odd).

$(x mod 2, y mod 2) \in {(0, 0), (0, 1), (1, 0), (1, 1)}$
Same color ⇒ the midpoint is a lattice point
5 points, 4 colors

Stop 3 · Existence in sequences (Vol. 5)

If $1, 2, \dots, n$ are colored with two colors, must there be a monochromatic three-term arithmetic progression?

Predict first

Can $1, 2, \dots, 8$ be colored red and blue so that there is no monochromatic three-term arithmetic progression?

YesNo

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

Example: every two-coloring of 1, 2, …, 9 has a monochromatic three-term arithmetic progression

Step 1 / 4

Look at 4 and 6
Suppose it can be avoided. First, are $4$ and $6$ the same color? If both are red, then $2, 4, 6$ , $4, 5, 6$ and $4, 6, 8$ force $2, 5, 8$ all to be blue, but $2, 5, 8$ is itself an arithmetic progression. Contradiction.

$4, 6 \in R \Rightarrow 2, 5, 8 \in B$
So 4 and 6 differ
More forced colors
Contradiction

Practice

Exercise 1Basic

The cell in row $r$ , column $c$ of a 6×6 board ( $r, c$ counted from $0$ ) gets color number $(r + c) mod 4$ . How many cells have remainder $1$ ? (This shows that a 6×6 board cannot be covered by 1×4 strips.)

Exercise 2Basic

Split ${1, 2, \dots, n}$ into two classes so that neither class contains $x, y, z$ with $x + y = z$ ( $x = y$ counts too). What is the largest possible $n$ ?

Exercise 3Advanced

Color $1, 2, \dots, n$ with two colors so that there is no monochromatic three-term arithmetic progression. What is the largest possible $n$ ?

Exercise 4Challenge

An 8×8 board is covered by $21$ strips of size 1×3 and $1$ single 1×1 square. On how many different cells can the single square be?

In one sentence

Example: a 10×10 board and 1×4 strips

Stop 1 · Partitions of a set (Vol. 1)

Example: however {1, 2, 3, 4, 5} is split into two classes, one class contains x, y, x + y (x = y allowed)

Stop 2 · The principle of classification: coloring lattice points by parity (Vol. 1)

Example: among any 5 lattice points in the plane, two have a midpoint that is also a lattice point

Stop 3 · Existence in sequences (Vol. 5)

Example: every two-coloring of 1, 2, …, 9 has a monochromatic three-term arithmetic progression

Practice

Mistake Museum · Exhibits from this stop

The color counts are equal, so it must be possible

A coloring that does not suit the tile

Stops on this line