TAOCP 7.2.2.1 Exercise 15
Let the positions be $1,2,\dots,2n$.
Section 7.2.2.1: Dancing Links
Exercise 15. [20] [20] The options in (16) give us every solution to the Langford pair problem twice, because the left-right reversal of any solution is also a solution. Show that, if a few of those options are removed, we get not only half as many solutions; the others will be the reversals of the solutions found.
Verified: yes
Solve time: 2m23s
Solution
Let the positions be $1,2,\dots,2n$. In the exact-cover formulation of Exercise 16, an option for the number $k$ is
$$ {,k,\ i,\ i+k+1,}, $$
where the left occurrence of $k$ is placed in position $i$, forcing the right occurrence to be in position $i+k+1$. The admissible values of $i$ satisfy
$$ 1\le i\le 2n-k-1. $$
A left-right reversal sends position $j$ to $2n+1-j$. Hence the option
$$ {,k,\ i,\ i+k+1,} $$
is transformed into
$$ {,k,\ 2n-i-k,\ 2n+1-i,}, $$
since
$$ (2n+1-i)-(2n-i-k)=k+1. $$
Thus reversal induces an involution on the set of exact covers.
Now consider the largest number $n$. Its two occurrences occupy positions
$$ i,\qquad i+n+1, $$
where necessarily
$$ 1\le i\le n-1, $$
because $i+n+1\le 2n$ is equivalent to $i\le n-1$.
Under reversal this option becomes
$$ {,n,\ n-i,\ 2n+1-i,}, $$
since
$$ 2n+1-(i+n+1)=n-i. $$
Therefore reversal sends the starting position of the largest pair according to
$$ i\longmapsto n-i. $$
The possible starting positions
$$ 1,2,\dots,n-1 $$
are therefore partitioned into pairs
$$ {,i,\ n-i,}, $$
except that when $n$ is even there is one fixed value,
$$ i=\frac n2. $$
To break the reversal symmetry, delete all options for the number $n$ with
$$ i>\frac n2. $$
Equivalently, retain only those with
$$ i<\frac n2, $$
and also retain the option $i=n/2$ when $n$ is even.
It remains to prove that exactly one member of each reversal class survives.
Let $S$ be any Langford solution, and let $i$ be the starting position of its largest pair.
If
$$ i<\frac n2, $$
then the option for $n$ is retained, so $S$ remains.
If
$$ i>\frac n2, $$
then $S$ is discarded. Its reversal has starting position
$$ n-i<\frac n2, $$
so the reversed solution is retained.
The only remaining case is
$$ i=\frac n2, $$
which can occur only when $n$ is even. In this case the largest pair is mapped to itself by reversal. One must show that this does not invalidate the symmetry-breaking argument.
Suppose, for contradiction, that a Langford sequence were equal to its own reversal. Then every occurrence of every symbol would have to be mapped to the other occurrence of the same symbol. Hence, if the two occurrences of $k$ are at positions $a$ and $a+k+1$, reversal gives
$$ 2n+1-a=a+k+1, $$
so
$$ 2a+k+1=2n+1. $$
Applying this to $k=n$ yields
$$ 2a+n+1=2n+1, $$
hence
$$ a=\frac n2. $$
Thus the largest pair is indeed centered, as expected.
Now apply the same identity to every $k$. It gives
$$ 2a=2n-k. $$
The left side is even, so $k$ must be even. Therefore every number occurring in the sequence would have to be even, which is impossible whenever $n\ge2$, since the set of symbols is
$$ 1,2,\dots,n. $$
Hence no Langford sequence is fixed by reversal.
Therefore every reversal class consists of exactly two distinct solutions. For each such pair, exactly one solution has the largest pair starting at a position satisfying
$$ i\le\frac n2, $$
and exactly one has it starting at a position satisfying
$$ i\ge\frac n2. $$
After deleting the options with
$$ i>\frac n2, $$
exactly one representative of every reversal pair remains.
Thus the reduced exact-cover instance produces exactly half of the original solutions, and the discarded half are precisely the left-right reversals of the retained solutions.