= Solution
The <Hales-Jewett theorem> states that for positive integers $m,k$ there is $N$ such that every $k$-coloring of the words $[m]^N$ contains a monochromatic <combinatorial line>.
Here is the standard focused-line proof. Induct on the alphabet size $m$, the case $m=1$ being immediate. Assume the result for $m-1$ and every number of colors. For $1\leq s\leq k$, prove inductively that some dimension has the following alternative: either there is a monochromatic combinatorial line, or there are $s$ color-focused lines, meaning that the lines without their common focus are monochromatic in $s$ distinct colors. For $s=1$, restrict to words on $[m-1]$ and use the induction hypothesis on $m$.
For the step from $s-1$ to $s$, let $n$ work for $s-1$ and view a longer word as $(a,b)\in[m]^n\times[m]^M$. Color each $b\in[m-1]^M$ by the complete pattern
$$
(c(a,b))_{a\in[m]^n},
$$
which uses at most $k^{m^n}$ colors. Taking $M=HJ(m-1,k^{m^n})$ gives a line on which this entire pattern is constant. Append its missing $m$-letter endpoint. Applying the $s-1$ alternative to the induced coloring of the first block and joining the active coordinate sets produces either a monochromatic line or $s$ lines with one common focus and distinct colors. At $s=k$, the focus has one of the $k$ colors, so it completes the line carrying that color. This proves the theorem.
To deduce the <Van der Waerden theorem>, let $N=HJ(m,k)$ and color a word $(x_1,\ldots,x_N)\in[m]^N$ by the color of $x_1+\cdots+x_N$. On a combinatorial line with active set $I$, these sums are
$$
A+|I|,A+2|I|,\ldots,A+m|I|,
$$
a monochromatic <arithmetic progression> of length $m$.
Back to article page
