TAOCP 7.2.2.2 Exercise 3

Exercise 3. ▶ [M21] [M21] Exactly how many clauses are in waerden$(j, k; n)$?

Verified: no
Solve time: 1m

Solution

The instance $\mathrm{waerden}(j,k;n)$ encodes the statement that every $j$-coloring of ${1,\ldots,n}$ contains a monochromatic arithmetic progression of length $k$. The variables are typically $x_{i,c}$, where $i \in {1,\ldots,n}$ and $c \in {1,\ldots,j}$, and the intended meaning is that $x_{i,c}$ is true when element $i$ receives color $c$.

A clause is introduced for each arithmetic progression of length $k$ together with each color $c \in {1,\ldots,j}$. If an arithmetic progression is

$$ a,\ a+d,\ a+2d,\ \ldots,\ a+(k-1)d, $$

then the forbidden event “all these $k$ positions receive color $c$” is represented by the clause

$$ \bar{x}{a,c} ;\vee; \bar{x}{a+d,c} ;\vee; \cdots ;\vee; \bar{x}_{a+(k-1)d,c}. $$

Each such clause is distinct, since it is determined uniquely by the pair $(a,d)$ and the color $c$.

The problem reduces to counting arithmetic progressions of length $k$ contained in ${1,\ldots,n}$. For a fixed common difference $d \ge 1$, the starting point $a$ must satisfy

$$ a + (k-1)d \le n, $$

which is equivalent to

$$ 1 \le a \le n - (k-1)d. $$

Hence, for this fixed $d$, the number of valid progressions is $n - (k-1)d$, provided this quantity is positive.

The admissible values of $d$ satisfy

$$ n - (k-1)d \ge 1, $$

which gives

$$ d \le \frac{n-1}{k-1}. $$

Thus $d$ ranges over $1 \le d \le m$, where

$$ m = \left\lfloor \frac{n-1}{k-1} \right\rfloor. $$

The total number of arithmetic progressions of length $k$ is therefore

$$ \sum_{d=1}^{m} \bigl(n - (k-1)d\bigr). $$

Each progression contributes exactly $j$ clauses, one for each color $c \in {1,\ldots,j}$, so the total number of clauses is

$$ j \sum_{d=1}^{m} \bigl(n - (k-1)d\bigr). $$

The sum evaluates as

$$ \sum_{d=1}^{m} \bigl(n - (k-1)d\bigr) = mn - (k-1)\sum_{d=1}^{m} d = mn - (k-1)\frac{m(m+1)}{2}. $$

Substituting this expression yields the total number of clauses:

$$ j \left( mn - (k-1)\frac{m(m+1)}{2} \right), \quad \text{where } m = \left\lfloor \frac{n-1}{k-1} \right\rfloor. $$

This completes the derivation. ∎

$$ \boxed{,j\left(mn - \frac{(k-1)m(m+1)}{2}\right), ;; m=\left\lfloor\frac{n-1}{k-1}\right\rfloor,} $$