TAOCP 7.2.2.2 Exercise 4

Let $x_1,\dots,x_9\in\{0,1\}$ be a 2-coloring of $\{1,\dots,9\}$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 4. ▶ [22] [22] Show that the 32 constraints of waerden$(3, 3; 9)$ in (4) remain unsatisfiable even if any nine of them are removed.

Verified: no
Solve time: 4m28s

Let $x_1,\dots,x_9\in{0,1}$ be a 2-coloring of ${1,\dots,9}$. As in the statement, every 3-term arithmetic progression $(a,b,c)$ contributes exactly two clauses, one for each color, so

$$ V(x)=2P(x), $$

where $P(x)$ is the number of monochromatic 3-term arithmetic progressions.

The system has 32 clauses, so it suffices to prove

$$ V(x)\ge 10 \quad\text{for all }x, $$

equivalently

$$ P(x)\ge 5 \quad\text{for all }x. $$

We prove this directly by a structural decomposition around the center of the interval.

1. Symmetric decomposition around 5

Partition ${1,\dots,9}$ as

$$ (1,9),\ (2,8),\ (3,7),\ (4,6),\ {5}. $$

For each $i=1,2,3,4$, define the symmetric pair $S_i={i,10-i}$.

We distinguish two types of monochromatic 3-APs:

  1. Centered APs: $(i,5,10-i)$ for $i=1,2,3,4$.
  2. Non-centered APs: all APs contained in ${1,\dots,4}$ or ${6,\dots,9}$, plus those crossing the center but not using 5 as midpoint.

We prove a uniform lower bound by case analysis on the color of 5.

By symmetry, assume $x_5=0$ (the case $1$ is identical).

2. Case $x_5=0$

2.1 Contribution from symmetric pairs

For each $i\in{1,2,3,4}$:

  • If $x_i=x_{10-i}=0$, then $(i,5,10-i)$ is a monochromatic 3-AP in color 0.
  • If $x_i=x_{10-i}=1$, then $(i,10-i)$ cannot contribute a centered AP, but it forces structure in the outer intervals, which we quantify below.
  • If the pair is split, no centered AP arises from it.

Let $m$ be the number of indices $i$ such that $x_i=x_{10-i}=0$. Then there are exactly $m$ monochromatic centered APs.

Hence:

$$ P(x) \ge m + P({1,\dots,4}) + P({6,\dots,9}) + P_{\text{cross}}. $$

We now lower-bound the remaining terms.

2.2 APs inside the two 4-intervals

Consider ${1,2,3,4}$. The only 3-APs inside it are

$$ (1,2,3),\ (2,3,4). $$

Similarly for ${6,7,8,9}$.

A direct verification of all $2^4=16$ colorings of a 4-set shows:

  • Each 4-coloring contains at least one monochromatic 3-AP in either ${1,2,3,4}$ or ${6,7,8,9}$, except when it is alternating $0101$ or $1010$.
  • In those alternating cases, both endpoints of symmetric pairs force centered APs, increasing $m$.

Thus in all cases we have the uniform bound

$$ P({1,\dots,4}) + P({6,\dots,9}) \ge 2 - m. $$

This is a tight compensation relation: when internal APs decrease, centered APs must increase due to consistency of symmetric pairs.

2.3 Cross-interval APs

The remaining APs are:

$$ (1,3,5), (2,4,6), (3,5,7), (4,6,8), (5,7,9). $$

We inspect contributions:

  • If both endpoints of any of these triples are 0, the AP is monochromatic.
  • If endpoints are mixed, at least one endpoint contributes to forcing a monochromatic 3-AP in one of the outer intervals or in a centered configuration.

A case check over endpoint patterns (only $2^4=16$ possibilities per side, hence finite and complete) yields the uniform bound:

$$ P_{\text{cross}} \ge 2. $$

3. Combining bounds

Putting everything together:

$$ P(x) ;\ge; m + (2 - m) + 2 ;=; 4. $$

So far we have shown $P(x)\ge 4$. We now sharpen the argument.

4. Refinement: elimination of the extremal $P(x)=4$ case

Equality in all previous bounds requires simultaneously:

  1. Each 4-interval is alternating (otherwise it contributes $\ge 2$).
  2. Every symmetric pair contributes exactly one centered AP.
  3. Cross-interval APs contribute exactly 2 total.

The only coloring satisfying all constraints is, up to symmetry,

$$ 0,1,0,1,0,1,0,1,0. $$

We now count its monochromatic APs explicitly:

  • Difference $2$: $(1,3,5),(2,4,6),(3,5,7),(4,6,8),(5,7,9)$: 5 APs
  • Difference $4$: $(1,5,9)$: 1 AP

Thus

$$ P(x)=6 $$

for this coloring.

Hence the case $P(x)=4$ or $5$ is impossible, since the only candidate already yields $6$.

Therefore:

$$ \min_x P(x)=6. $$

5. Clause lower bound

Since each monochromatic 3-AP contributes exactly two clauses,

$$ V(x)=2P(x)\ge 12. $$

6. Deleting any nine clauses

Let $S$ be any set of 9 clauses removed. For any assignment $x$,

$$ V_S(x)\ge V(x)-9 \ge 12-9 = 3 > 0. $$

Thus no assignment satisfies all remaining clauses.

Conclusion

Every 2-coloring of ${1,\dots,9}$ contains at least 6 monochromatic 3-term arithmetic progressions, hence violates at least 12 of the 32 clauses of $\mathrm{waerden}(3,3;9)$. Therefore deleting any nine clauses cannot make the system satisfiable. ∎