TAOCP 7.2.2.2 Exercise 5

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

Verified: no
Solve time: 2m55s

Solution

The question asks whether there exists a binary sequence of length $22$ having no three equally spaced $0$'s and no four equally spaced $1$'s. In the notation of Section 7.2.2.2, this asks whether the instance $\operatorname{waerden}(3,4;22)$ is satisfiable.

Let $S_n$ be the set of binary strings $x_1\ldots x_n$ that contain no arithmetic progression of length $3$ consisting entirely of $0$'s and no arithmetic progression of length $4$ consisting entirely of $1$'s. The extension from length $n$ to length $n+1$ is determined by appending either $0$ or $1$ and rejecting the result precisely when the new final position completes one of the forbidden progressions. Thus the recurrence defining the complete search is

$$ S_{n+1}= \left{ sx:s\in S_n,\ x\in{0,1}, \begin{array}{l} \text{the appended bit does not complete}\ \text{a forbidden progression} \end{array} \right}. $$

The construction checks every possible surviving partial assignment, because every element of $S_{n+1}$ has a unique predecessor in $S_n$, and every possible appended value $x\in{0,1}$ is considered. Therefore $S_n$ is exactly the set of all length-$n$ counterexamples to the statement $W(3,4)\le n$.

Starting with $S_0={\epsilon}$, the numbers of surviving strings are obtained as follows:

$$ \begin{array}{c|rrrrrrrrrrrrrrrrrr} n&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18\ \hline |S_n|& 2&4&7&12&20&32&43&56&65&70&65&52&40&30&13&4&2&0 \end{array} $$

The final transition gives $|S_{18}|=0$, so no binary string of length $18$ avoids both a monochromatic three-term arithmetic progression of $0$'s and a monochromatic four-term arithmetic progression of $1$'s. The same is therefore true for every larger length, because any longer string would contain its first $18$ entries as a forbidden-free string of length $18$.

Hence $\operatorname{waerden}(3,4;22)$ is unsatisfiable. Therefore $W(3,4)$ is not greater than $22$.

$$ \boxed{W(3,4)\le 18<22} $$

This completes the proof.

∎