TAOCP 7.2.2.2 Exercise 409

Exercise 409. ▶ [M26] [M26] Continuing exercise 408, find the best makespans in the following cases:

a) $m = 3$; $n = 3t + 1$; $w_{1j} = w_{2(j+1)} = w_{3(j+s)} = a_j$ for $1 \le j \le r$; $w_{1n} = w_{2n} = w_{3n} = \lfloor (a_1 + \cdots + a_r)/2 \rfloor$; otherwise $w_{ij} = 0$. (The positive integers $a_j$ are given.)

b) $m = 4$; $n = r + 2$; $w_{1j} = (r+1)a_j$ and $w_{2j} = 1$ for $1 \le j \le r$; $w_{2(r+1)} = w_{2r} = (r+1)\lfloor (a_1 + \cdots + a_r)/2 \rfloor$; $w_{4n} = w_{4n} = w_{4r} = r - 1$; otherwise $w_{ij} = 0$.

c) $m = n$; $w_{jj} = n - 2$; $w_{jn} = w_{nj} = 1$ for $1 \le j < n$; otherwise $w_{ij} = 0$.

d) $m = 2$; $w_{1j} = a_j$ and $w_{2j} = b_j$ for $1 \le j \le n$, where $a_1 + \cdots + a_n = b_1 + \cdots + b_n = s$ and $a_j + b_j \le s$ for all $j$.

Verified: no
Solve time: 3m48s

Solution

Number the rows and columns of the diagram from $0$ to $3$. A rearrangement that works is

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

The phrase to be traced, ignoring the separators, is

$$ \text{THEARTOFCOMPUTERPROGRAMMING}. $$

A sequence of positions that traces this phrase is

$$ \begin{aligned} &(0,0),(0,1),(0,2),(0,3),(1,1),(0,0),(1,2),(1,3),(2,1),\ &(1,2),(2,2),(3,0),(2,0),(1,0),(0,2),(1,1),(3,0),\ &(1,1),(1,2),(2,3),(1,1),(0,3),(2,2),(3,1),(3,2),\ &(3,3),(2,3). \end{aligned} $$

Reading the letters in these positions gives

$$ \begin{aligned} &T,H,E,A,R,T,O,F,C,O,M,P,U,T,E,R\ &\qquad P,R,O,G,R,A,M,M,I,N,G, \end{aligned} $$

which is exactly

$$ \text{THE_ART_OF_COMPUTER_PROGRAMMING}. $$

For consecutive positions in the displayed path, the displacement is always either a king move, meaning that the row and column changes are each at most $1$, or a knight move, meaning that the absolute changes are $1$ and $2$ in some order. The only repeated type of move that needs checking is the transition between the final occurrences of letters, and the last transition is

$$ (3,3)\rightarrow(2,3), $$

which is a king move. Thus the former exceptional step from $R$ to $G$ has also been replaced by a legal move.

Therefore the rearranged diagram above permits the complete phrase to be traced using only king moves and knight moves.

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

This completes the solution. ∎