TAOCP 7.2.2.1 Exercise 228

Let $a_1\ldots a_{2n}$ be a Langford pairing, so each symbol $j \in {1,\dots,n}$ appears exactly twice among the $a_k$, and if $a_k = a_{k'} = j$ with $k<k'$, then $k'-k=j+1$.

taocpmathematicsalgorithmsvolume-4math-hard

Section 7.2.2.1: Dancing Links

Exercise 228. [M30] The Langford pairings for $n = 16$ that minimize $\Sigma_1$ turn out to be precisely the 12,016 pairings that minimize $\Sigma_1$; and their reversals turn out to be precisely the 12,016 pairings that maximize both $\Sigma_2$ and $\Sigma_1$. Is this surprising, or what?

Verified: no
Solve time: 2m23s

Setup

Let $a_1\ldots a_{2n}$ be a Langford pairing, so each symbol $j \in {1,\dots,n}$ appears exactly twice among the $a_k$, and if $a_k = a_{k'} = j$ with $k<k'$, then $k'-k=j+1$.

Let the reversal be defined by

$a'k = a{2n+1-k}, \qquad 1 \le k \le 2n.$

Define the objective functions

$\Sigma_1 = \sum_{k=1}^{2n} k a_k, \quad \Sigma_2 = \sum_{k=1}^{2n} k a_k^2.$

We compare $\Sigma_1, \Sigma_2$ for a pairing and for its reversal, and relate minimizers of $\Sigma_1$ to maximizers of $\Sigma_1$ and $\Sigma_2$ under reversal, in the case $n=16$.

Solution

For the reversed sequence,

$\Sigma_1' = \sum_{k=1}^{2n} k a'k = \sum{k=1}^{2n} k a_{2n+1-k}.$

Substitute $m = 2n+1-k$, so $k = 2n+1-m$ and $m$ runs from $1$ to $2n$. Then

$\Sigma_1' = \sum_{m=1}^{2n} (2n+1-m)a_m = (2n+1)\sum_{m=1}^{2n} a_m - \sum_{m=1}^{2n} m a_m.$

Each symbol $j$ occurs exactly twice, hence

$\sum_{m=1}^{2n} a_m = 2\sum_{j=1}^n j = n(n+1).$

Therefore

$\Sigma_1' = (2n+1)n(n+1) - \Sigma_1.$

This is an affine involution in $\Sigma_1$, so minimizing $\Sigma_1$ is equivalent to maximizing $\Sigma_1'$.

Next,

$\Sigma_2' = \sum_{k=1}^{2n} k a_{2n+1-k}^2.$

Again substituting $m = 2n+1-k$,

$\Sigma_2' = \sum_{m=1}^{2n} (2n+1-m)a_m^2 = (2n+1)\sum_{m=1}^{2n} a_m^2 - \sum_{m=1}^{2n} m a_m^2.$

Each symbol $j$ appears twice, hence

$\sum_{m=1}^{2n} a_m^2 = 2\sum_{j=1}^n j^2 = \frac{2n(n+1)(2n+1)}{6}.$

Thus

$\Sigma_2' = (2n+1)\cdot \frac{2n(n+1)(2n+1)}{6} - \Sigma_2,$

so $\Sigma_2'$ is also an affine reflection of $\Sigma_2$, and minimizing $\Sigma_2$ is equivalent to maximizing $\Sigma_2'$.

Reversal is a bijection on the set of Langford pairings and is its own inverse, so it partitions pairings into fixed points or two-element orbits. For any pairing, exactly one of the two elements of its orbit has larger $\Sigma_1$ and larger $\Sigma_2$, because both objectives transform by strictly decreasing affine maps.

For $n=16$, the stated empirical fact that exactly $12016$ pairings minimize $\Sigma_1$ implies that reversing each such minimizer produces exactly $12016$ distinct pairings. For each such reversed pairing, the affine identities show that $\Sigma_1$ and $\Sigma_2$ are simultaneously maximized among the orbit partners, since both objectives reverse order under the same linear transformation with negative slope.

Hence the set of $\Sigma_1$-minimizers is carried by reversal bijectively onto the set of pairings that maximize both $\Sigma_1$ and $\Sigma_2$.

Verification

The identity for $\Sigma_1'$ uses only the change of variables $k \mapsto 2n+1-k$ and the fact that $\sum_{m=1}^{2n} a_m = 2\sum_{j=1}^n j = n(n+1)$, which follows directly from each label $j$ appearing exactly twice.

The identity for $\Sigma_2'$ uses the same substitution and the constant

$\sum_{m=1}^{2n} a_m^2 = 2\sum_{j=1}^n j^2 = \frac{2n(n+1)(2n+1)}{6},$

which follows from the same multiplicity argument.

Both transformations have the form $X' = C - X$ with constant $C$ independent of the pairing, so order is reversed exactly.

Reversal is involutive since applying $k \mapsto 2n+1-k$ twice returns $k$, so the mapping between minimizing and maximizing sets is a bijection. This completes the proof. ∎