TAOCP 7.2.2.2 Exercise 5

Let $W(3,4)$ denote the least $n$ such that every 2-coloring of ${1,\ldots,n}$ contains a monochromatic arithmetic progression of length $3$ in color $1$ or length $4$ in color $2$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.2.2: Satisfiability

Exercise 5. [M20] [M20] Is $W(3, 4)$ even $> 22$?

Verified: no
Solve time: 59s

Solution

Let $W(3,4)$ denote the least $n$ such that every 2-coloring of ${1,\ldots,n}$ contains a monochromatic arithmetic progression of length $3$ in color $1$ or length $4$ in color $2$.

The value $W(3,4)$ is determined earlier in the van der Waerden computations as

$W(3,4)=18.$

Since $18=2\cdot 9$, the number $W(3,4)$ is even.

Since $18 \le 22$, the statement $W(3,4) > 22$ is false.

Thus $W(3,4)$ is even and not greater than $22$.

This completes the proof. ∎