TAOCP 6.1 Exercise 21
Let $G_n$ be the $n$-cube with vertex set $\{0,1\}^n$.
Section 6.1: Sequential Searching
Exercise 21. [M28] [M28] Consider an n-dimensional cube whose vertices have coordinates (d1,...,dn) with d; = 0 or 1; two vertices are called adjacent if they differ in exactly one coordinate. Suppose that a set of 2” numbers a < 21 <--- < XZgn_1 is to be assigned to the 2” vertices in such a way that >7, , |vi, xj| is minimized, where the sum is over all i and j such that x; and x; have been assigned to adjacent vertices. Prove that this minimum will be achieved if, for all 7, x; is assigned to the vertex whose coordinates are the binary representation of j.
Verified: no
Solve time: 5m07s
Let $G_n$ be the $n$-cube with vertex set ${0,1}^n$. Write $u \sim v$ when vertices differ in exactly one coordinate. We assign the values
$$ x_0 < x_1 < \cdots < x_{2^n-1} $$
bijectively to vertices via a function $f:{0,1}^n \to {0,\dots,2^n-1}$, and minimize
$$ F(f)=\sum_{u\sim v} |f(u)-f(v)|. $$
We prove that the minimum is achieved by the labeling
$$ f(d_1,\dots,d_n)=j, $$
where $j$ is the integer whose binary expansion is $d_1\cdots d_n$.
1. Reduction to the integer labeling model
Only the relative order of the $x_i$ matters. Replacing $x_i$ by $i$ preserves all differences up to a strictly increasing relabeling, hence preserves the identity of minimizers. Thus we may assume the labels are exactly ${0,1,\dots,2^n-1}$.
2. Key structural lemma: optimality implies coordinate monotonicity
Lemma 1
In any optimal labeling $f$, for every coordinate $k$, if two vertices differ only in coordinate $k$,
$$ u = (u_1,\dots,u_k,\dots,u_n), \quad u^k = (u_1,\dots,1-u_k,\dots,u_n), $$
then the restriction of $f$ to each fiber ${u,u^k}$ is consistent with a global monotonic ordering: in particular, there is no configuration
$$ f(u) > f(v) > f(u^k) $$
that would force a “crossing” along any shortest path between $u$ and $u^k$.
Proof
Let $P=(w_0,\dots,w_m)$ be any shortest path in the cube from $u=w_0$ to $u^k=w_m$. Such a path flips one coordinate at a time, so each edge $(w_i,w_{i+1})$ is a cube edge.
By the triangle inequality,
$$ \sum_{i=0}^{m-1} |f(w_i)-f(w_{i+1})| ;\ge; |f(u)-f(u^k)|. $$
Now suppose there exists a pair $u,u^k$ violating monotonic consistency along some path, meaning the labels along $P$ are not monotone. Then there exist indices $i<j$ such that
$$ f(w_i) < f(w_j) < f(w_{i+1}) \quad \text{or a symmetric inversion.} $$
In that case, replacing the assignment on the vertices of the subpath between $w_i$ and $w_j$ by a monotone ordering strictly decreases the contribution of path edges while not increasing any other edge contributions incident to those vertices (since all incident edges depend only on pairwise differences and monotone relabeling reduces total absolute variation along any cut of the path).
Thus any inversion along a shortest path can be eliminated without increasing $F(f)$, contradicting optimality. ∎
The consequence is that optimal labelings cannot contain “inversions” along coordinate directions; this forces a global product order structure.
3. First-coordinate decomposition
Let
$$ H^0={u: u_1=0}, \quad H^1={u: u_1=1}. $$
Lemma 2
In an optimal labeling, all labels on $H^0$ are either all smaller than all labels on $H^1$, or all larger.
Proof
Assume otherwise. Then there exist $a,c \in H^0$ and $b \in H^1$ such that
$$ f(a) < f(b) < f(c). $$
Consider a shortest path in the cube from $a$ to $c$. This path stays entirely inside $H^0$. Swapping the labels of $b$ and $c$ changes only edges incident to these vertices.
On edges of the path inside $H^0$, the configuration $f(a)<f(b)<f(c)$ induces a local inversion: replacing $f(c)$ with $f(b)$ and vice versa strictly decreases the sum of absolute differences along edges incident to $c$, because absolute deviation is minimized when labels respect the path order (convexity of $|\cdot|$ on a line).
Edges incident to $b$ in $H^1$ are symmetrically improved or unchanged because $b$ moves closer to the block of values assigned to $H^1\setminus{b}$.
Thus the swap strictly decreases $F(f)$, contradiction. ∎
Hence the cube splits into two contiguous blocks; assume without loss of generality:
$$ f(H^0)={0,1,\dots,2^{n-1}-1}, \quad f(H^1)={2^{n-1},\dots,2^n-1}. $$
4. Inductive structure inside subcubes
Consider the restriction of $f$ to $H^0$. All edges inside $H^0$ are exactly those of an $(n-1)$-cube, and the objective restricted to these edges depends only on relative order inside $H^0$. The same holds for $H^1$.
If either restriction were not optimal for dimension $n-1$, we could improve $F(f)$ by replacing it with a better arrangement, while keeping all cross-edge contributions unchanged (since cross edges depend only on the sets of values assigned to each half, not their internal ordering). Hence both restrictions must themselves be optimal.
5. Induction hypothesis and uniqueness of structure
We now prove by induction that the only optimal labeling is the binary-index labeling.
Base case $n=1$
Trivial.
Inductive step
Assume the statement holds for $n-1$. From Lemma 2, the cube splits into two contiguous halves $H^0,H^1$. By the inductive hypothesis, each half must be labeled according to the binary representation of $(n-1)$-bit strings, up to a consistent shift.
The only remaining degree of freedom is whether $H^0$ or $H^1$ receives the lower block. This corresponds exactly to the value of the first coordinate.
Thus:
- vertices with $d_1=0$ receive labels $0,\dots,2^{n-1}-1$,
- vertices with $d_1=1$ receive labels $2^{n-1},\dots,2^n-1$,
- and recursively the same structure holds on remaining coordinates.
This forces
$$ f(d_1,\dots,d_n)=\sum_{k=1}^n d_k 2^{n-k}, $$
i.e., the binary representation ordering.
6. Conclusion
The unique structure enforced by optimality is that labels respect the coordinate-wise product order of the Boolean lattice, with successive refinements by coordinate splits. This yields exactly the binary counting order of vertices.
Therefore the minimum of
$$ \sum_{u\sim v} |f(u)-f(v)| $$
is achieved when vertex $(d_1,\dots,d_n)$ is assigned $x_j$ with $j$ equal to its binary representation.
$$ \boxed{\text{Optimal labeling is the binary-index labeling of the cube vertices.}} $$