TAOCP 7.2.2.1 Exercise 227
In the Langford pairing exact cover formulation for $n=4$, options are indexed lexicographically by $(k,i)$ where $k$ is the value and $i$ is the first position, with the second position $j=i+k+1$.
Section 7.2.2.1: Dancing Links
Exercise 227. [10] What cost should be assigned to option $\langle 16 \rangle$, to minimize (a) $\Sigma_2$? (b) $S$?
Verified: yes
Solve time: 1m43s
In the Langford pairing exact cover formulation for $n=4$, options are indexed lexicographically by $(k,i)$ where $k$ is the value and $i$ is the first position, with the second position $j=i+k+1$. Hence option $\langle 16\rangle$ corresponds to $k=4$ and $i=1$, giving positions $1$ and $6$.
For $\Sigma_2=\sum_{k=1}^{2n} k a_k^2$, the contribution of placing value $v$ at positions $i$ and $j$ is $v^2 i + v^2 j = v^2(i+j)$. For option $\langle 16\rangle$, this is
$4^2(1+6)=16\cdot 7=112.$
For $S=\sum_{k=1}^{2n} k a_k^3$, the analogous contribution is $v^3(i+j)$. For option $\langle 16\rangle$, this is
$4^3(1+6)=64\cdot 7=448.$
Assigning these values to option $\langle 16\rangle$ yields the minimal contributions consistent with the respective objective functions, since each option contributes additively and independently to $\Sigma_2$ and $S$ under the Langford encoding.
$\boxed{\text{(a) }112,\ \text{(b) }448}$