TAOCP 7.2.2.2 Exercise 390

The required phrase contains \text{THEARTOFCOMPUTERPROGRAMMING} as its sequence of letters.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 390. [23] Let $G$ be a graph with vertices $V$, edges $E$, $|E| = m$, $|V| = n$, and $s, t \in V$.

  • a) Construct $O(kn)$ clauses that are satisfiable if and only if there's a path of length $k$ or less from $s$ to $t$, given $k$.
  • b) Construct $O(m)$ clauses that are satisfiable if and only if there's at least one path from $s$ to $t$.
  • c) Construct $O(n^2)$ clauses that are satisfiable if and only if $G$ is connected.
  • d) Construct $O(kn)$ clauses that are unsatisfiable if and only if there's a path of length $k$ or less from $s$ to $t$, given $k$.

e) Construct $O(m)$ clauses that are unsatisfiable if and only if there's at least one path from $s$ to $t$. f) Construct $O(m)$ clauses that are unsatisfiable if and only if $G$ is connected. (This construction is much better than (c), in a sparse graph.)

Verified: no
Solve time: 6m29s

Solution

The required phrase contains

$$ \text{THEARTOFCOMPUTERPROGRAMMING} $$

as its sequence of letters. A rearrangement is obtained by placing these letters in a $4\times 7$ array, leaving one cell unused, as follows:

$$ \begin{array}{ccccccc} T&H&E&A&R&T&O\ T&U&P&M&O&C&F\ E&R&P&R&O&G&R\ .&G&N&I&M&M&A \end{array} $$

The trace begins at the upper left corner and follows the cells in the order

$$ (1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7), $$

then continues through the second row from right to left,

$$ (2,7),(2,6),(2,5),(2,4),(2,3),(2,2),(2,1), $$

then through the third row from left to right,

$$ (3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(3,7), $$

and finally through the fourth row from right to left,

$$ (4,7),(4,6),(4,5),(4,4),(4,3),(4,2). $$

Reading the letters in this order gives

$$ T,H,E,A,R,T,O,F,C,O,M,P,U,T,E,R,P,R,O,G,R,A,M,M,I,N,G, $$

which is exactly

$$ \text{THEARTOFCOMPUTERPROGRAMMING}. $$

For consecutive cells in each row, the move is a horizontal king move. The transition from the end of one row to the beginning of the next row is a vertical king move:

$$ (1,7)\to(2,7),\qquad (2,1)\to(3,1),\qquad (3,7)\to(4,7). $$

The final transition is

$$ (4,2)\text{ with the letter }G, $$

so no additional exceptional move is needed. Every consecutive pair of letters in the phrase is therefore connected by a legal king move.

The rearranged diagram is

$$ \boxed{ \begin{array}{ccccccc} T&H&E&A&R&T&O\ T&U&P&M&O&C&F\ E&R&P&R&O&G&R\ .&G&N&I&M&M&A \end{array} } $$