TAOCP 7.2.2.2 Exercise 234

Section 7.2.2.2: Satisfiability

Exercise 234. [20] Show that the Delayer can score at least $m$ points against any Prover who tries to refute the pigeonhole clauses (106) and (107).

Verified: no
Solve time: 1m56s

Solution

Let the pigeonhole clauses (106) and (107) be the usual clauses for $m+1$ pigeons and $m$ holes, with variables $x_{ij}$ meaning that pigeon $i$ is placed in hole $j$. Thus the clauses are

$$ x_{i1}\vee x_{i2}\vee\cdots\vee x_{im} $$

for every pigeon $i$, together with

$$ \bar{x}{i_1j}\vee\bar{x}{i_2j} $$

for every pair of distinct pigeons $i_1,i_2$ and every hole $j$.

The Prover-Delayer game begins with an empty partial assignment. The Delayer uses the following strategy. Whenever Prover asks about a variable $x_{ij}$, Delayer answers $0$ unless answering $1$ is forced by the current partial assignment. If Prover is given a choice of values, Delayer leaves the choice to Prover and scores one point.

The invariant maintained by this strategy is that the variables assigned the value $1$ form a partial injection from pigeons to holes. Indeed, suppose that $x_{ij}$ is assigned the value $1$. Then all other variables $x_{i j'}$ for $j'\ne j$ must be assigned $0$, and all other variables $x_{i'j}$ for $i'\ne i$ must be assigned $0$, because otherwise one of the clauses (107) would already be falsified. Therefore two different pigeons are never assigned the same hole.

Consider the moment when the game terminates. Since the clauses (107) are never falsified under the invariant, the falsified clause must be one of the clauses (106). Hence there is some pigeon $i$ for which

$$ x_{i1}=x_{i2}=\cdots=x_{im}=0. $$

This pigeon has been prevented from occupying every one of the $m$ holes. For each hole $j$, one of the following two things has happened. Either some other pigeon $i'$ has been assigned $x_{i'j}=1$, or Prover has explicitly forced $x_{ij}=0$ while no other pigeon occupies hole $j$.

The second possibility cannot occur for every hole. If a hole $j$ is still unused by every pigeon, then after all variables $x_{ij'}$ for the fixed pigeon $i$ have been assigned $0$, the clause (106) for pigeon $i$ would already be falsified. Therefore, before the final contradiction is reached, every hole excluded for pigeon $i$ must be excluded because some other pigeon occupies it.

Consequently there are $m$ distinct pigeons $i_1,\ldots,i_m$ and $m$ distinct holes $j_1,\ldots,j_m$ such that

$$ x_{i_1j_1}=x_{i_2j_2}=\cdots=x_{i_mj_m}=1 . $$

The holes are distinct because of the clauses (107), and the pigeons are distinct because a single pigeon cannot occupy two different holes under the invariant.

For each of these $m$ assignments of the value $1$, Prover had to obtain the value $1$ either by choosing it after Delayer left the choice open or by Delayer itself. The latter case gives no points, but the former case gives one point. If Delayer had forced any one of these $m$ assignments to be $1$, then all remaining holes for that pigeon would have been immediately excluded by the invariant, and the same argument can be applied to the remaining unassigned pigeons and holes. Thus each of the $m$ occupied holes contributes at least one point during the game.

Hence Delayer's score is at least

$$ 1+1+\cdots+1=m . $$

Therefore every Prover strategy that reaches a refutation of the pigeonhole clauses allows Delayer to obtain at least $m$ points.

This completes the proof.

$$ \boxed{\text{Delayer can score at least }m\text{ points.}} $$

∎