TAOCP 7.2.2.2 Exercise 3

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

Verified: yes
Solve time: 1m30s

Solution

By the definition of $\operatorname{waerden}(j,k;n)$, the clauses are divided into two families. The positive clauses are

$$ (x_i\vee x_{i+d}\vee\cdots\vee x_{i+(j-1)d}) $$

with

$$ 1\leq i\leq n-(j-1)d,\qquad d\geq1, $$

and the negative clauses are

$$ (\bar{x}i\vee\bar{x}{i+d}\vee\cdots\vee\bar{x}_{i+(k-1)d}) $$

with

$$ 1\leq i\leq n-(k-1)d,\qquad d\geq1. $$

For a fixed value of $d$ in the positive family, the number of possible starting positions $i$ is

$$ n-(j-1)d. $$

The allowed values of $d$ are exactly those satisfying

$$ n-(j-1)d\geq1, $$

or equivalently,

$$ d\leq\left\lfloor\frac{n-1}{j-1}\right\rfloor . $$

Therefore the number of positive clauses is

$$ \sum_{d=1}^{\left\lfloor (n-1)/(j-1)\right\rfloor} \bigl(n-(j-1)d\bigr). $$

The same argument applied to the negative family gives

$$ \sum_{d=1}^{\left\lfloor (n-1)/(k-1)\right\rfloor} \bigl(n-(k-1)d\bigr) $$

negative clauses.

Hence the total number of clauses in $\operatorname{waerden}(j,k;n)$ is

$$ \boxed{ \sum_{d=1}^{\left\lfloor (n-1)/(j-1)\right\rfloor} \bigl(n-(j-1)d\bigr) + \sum_{d=1}^{\left\lfloor (n-1)/(k-1)\right\rfloor} \bigl(n-(k-1)d\bigr) }. $$

Equivalently, if

$$ a=\left\lfloor\frac{n-1}{j-1}\right\rfloor, \qquad b=\left\lfloor\frac{n-1}{k-1}\right\rfloor , $$

then the two arithmetic sums give

$$ an-(j-1)\frac{a(a+1)}2 + bn-(k-1)\frac{b(b+1)}2 . $$

Thus another form of the answer is

$$ \boxed{ n(a+b)-\frac{(j-1)a(a+1)+(k-1)b(b+1)}2 } $$

with $a$ and $b$ defined above.