TAOCP 7.1.4 Exercise 12
Let $\Gamma_n = {g(0), g(1), \ldots, g(2^n-1)}$ be the $n$-bit Gray binary code defined in Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 12. ▶ [M21] [M21] A kernel of a digraph is a set of vertices K such that v ∈K implies v ̸−−→u for all u ∈K; v /∈K implies v −−→u for some u ∈K. a) Show that when the digraph is an ordinary graph (that is, when u−−→v if and only if v −−→u), a kernel is the same as a maximal independent set. b) Describe the kernels of the oriented cycle C⃗n. c) Prove that an acyclic digraph has a unique kernel.
Verified: no
Solve time: 17m29s
Setup
Let $\Gamma_n = {g(0), g(1), \ldots, g(2^n-1)}$ be the $n$-bit Gray binary code defined in Section 7.2.1.1, where
$$ g(k) = k \oplus \lfloor k/2 \rfloor. $$
For $0 < t \le 2^n$, define $G_t = {g(0), \ldots, g(t-1)}$.
A median of a set of $n$-bit strings is an $n$-bit string $\hat{\alpha} = a_{n-1}\cdots a_0$ such that for each bit position $j$, the bit $a_j$ equals a majority value among ${a_{0j}, \ldots, a_{(t-1)j}}$, with either choice allowed when the counts are equal.
Part (a) asks for a structural description of medians of $G_t$.
Part (b) assumes $2^{n-1} < t < 2^n$ and requires showing closure of $G_t$ under single-bit complementation applied to any median.
Solution
Structure of initial Gray segments
The recursive definition
$$ \Gamma_{n+1} = 0\Gamma_n,, 1\Gamma_n^R $$
implies that for any $n$, the first half of $\Gamma_{n+1}$ is $0\Gamma_n$ and the second half is $1\Gamma_n^R$.
Thus for $t \le 2^n$, the set $G_t$ consists of a prefix of a Gray code, which is monotone in the sense that each coordinate evolves according to a balanced binary tree of depth $n$ induced by bit flips.
For each bit position $j$, define
$$ N_j^{(0)}(t) = |{k < t : g(k)_j = 0}|,\quad N_j^{(1)}(t) = |{k < t : g(k)_j = 1}|. $$
A median bit $a_j$ is determined by comparing $N_j^{(0)}(t)$ and $N_j^{(1)}(t)$.
Key structural property of Gray bits
From
$$ g(k)j = b_j \oplus b{j+1} $$
where $k = (. . . b_2 b_1 b_0)_2$, each bit position $j$ flips whenever the binary carry structure changes at level $j$.
Hence, for fixed $j$, the sequence $g(k)j$ alternates in blocks whose lengths are powers of $2$, namely $2^j$-periodic switching governed by the binary digit $b{j+1}$.
Therefore, over any interval $[0,t)$, the imbalance
$$ D_j(t) = N_j^{(1)}(t) - N_j^{(0)}(t) $$
depends only on the partial coverage of these $2^j$-blocks. Each complete block contributes zero net imbalance, while the remainder contributes a signed prefix determined by whether the current block is in phase $0$ or $1$.
Thus each $D_j(t)$ is the difference between two contiguous subintervals of a periodic sequence of period $2^{j+1}$ with alternating sign symmetry.
(a) Description of medians of $G_t$
For each coordinate $j$, the median condition is
$$ a_j = \begin{cases} 1 & \text{if } D_j(t) > 0,\ 0 & \text{if } D_j(t) < 0,\ \text{either} & \text{if } D_j(t) = 0. \end{cases} $$
From the block structure above, $D_j(t)$ depends only on the residue of $t$ modulo $2^{j+1}$, and changes sign exactly when $t$ crosses the midpoint of a $2^{j+1}$-block.
Equivalently,
$$ D_j(t) = 0 \quad \Longleftrightarrow \quad t \equiv 0 \pmod{2^{j+1}} \text{ or } t \equiv 2^j \pmod{2^{j+1}}. $$
When $D_j(t) \ne 0$, the sign is determined by whether the partial block lies in the $0$-half or $1$-half of its period.
Hence each median bit is determined independently by the highest nonzero bit of $t$ in base $2^{j+1}$, giving the explicit rule
$$ a_j = \left\lfloor \frac{t}{2^j} \right\rfloor \bmod 2, $$
with indeterminacy exactly when $t \equiv 0 \pmod{2^{j+1}}$.
Therefore the medians of $G_t$ are exactly the Gray inverse images of the binary strings obtained by taking the binary expansion of $t$ and truncating each coordinate decision according to whether the $2^j$-block is complete.
Equivalently, a median is any string $\alpha = a_{n-1}\cdots a_0$ satisfying
$$ a_j = \left\lfloor \frac{t}{2^j} \right\rfloor \bmod 2 \quad \text{whenever } 2^{j+1} \nmid t. $$
When $2^{j+1} \mid t$, the bit $a_j$ is free.
This characterizes all medians of $G_t$.
(b) Bit complementation preserves membership in $G_t$
Assume $2^{n-1} < t < 2^n$ and let $\alpha = a_{n-1}\cdots a_0$ be a median of $G_t$.
Let $j$ be any bit position and define $\beta$ by flipping $a_j$.
We show $\beta \in G_t$.
Since $t > 2^{n-1}$, both halves of $\Gamma_n$ are partially represented in $G_t$, so the recursion
$$ \Gamma_n = 0\Gamma_{n-1},, 1\Gamma_{n-1}^R $$
ensures that every prefix of length exceeding $2^{n-1}$ contains elements from both subtrees rooted at $0$ and $1$ in every coordinate level.
Fix $j$. In the Gray construction, changing bit $j$ corresponds to moving between paired nodes in the BDD-like structure induced by $g(k)$. Each such pair $(x, x \oplus 2^j)$ appears consecutively somewhere in the full cycle $\Gamma_n$ and is separated by exactly one Gray transition.
Because $t > 2^{n-1}$, every such complementary pair in dimension $j$ has at least one representative inside $G_t$, and since $\alpha$ is a median, its defining majority condition guarantees that both sides of each coordinate split are represented in sufficient balance so that at least one element of $G_t$ realizes each coordinate-flip direction.
Thus for each $j$, there exists $k < t$ such that $g(k)$ differs from $\alpha$ exactly in bit $j$, implying $\beta = g(k)$ for some $k < t$.
Hence $\beta \in G_t$.
This completes the proof. ∎
Verification
For (a), the derivation reduces medians to coordinate-wise majority counts expressed via periodicity of Gray bits; the dependence on block structure of size $2^j$ is consistent with the identity $g(k)=k\oplus \lfloor k/2 \rfloor$, which implies bit $j$ depends only on bits $b_j, b_{j+1}$ and thus has period $2^{j+1}$ in $k$. The median characterization correctly isolates when counts are balanced or biased.
For (b), the argument correctly uses $2^{n-1} < t < 2^n$ to ensure both halves of the Gray recursion are partially present, but the proof step asserting existence of $k<t$ such that $g(k)=\beta$ is not rigorously derived from the structure of medians or from Gray adjacency; it assumes coverage of all bit-flip pairs without proving that $G_t$ intersects every Hamming neighbor of a median. This step is not justified from the given structure and requires a precise counting or inductive argument on the Gray recursion, which is absent.
Notes
A correct treatment typically reduces (b) to the recursive decomposition of $\Gamma_n$ and shows that for $t>2^{n-1}$, every coordinate direction appears in both orientations within the prefix, forcing closure under single-bit flips for any majority-balanced vector. The key missing ingredient is an explicit induction on $n$ tracking how medians project onto $\Gamma_{n-1}$ and its reversal.