TAOCP 6.5 Exercise 9

Section 6.5: Retrieval on Secondary Keys

Exercise 9. [M20] [M20] Prove that when v = 3”, the set of all triples of the form {(a1 «++ Qk-1 0 by wae bn, k)3, (ai ++» QAk-1 1 C1... Cn, k)3, (a1 ~.-Ak-1 2d, wae dn, k)3}, 1<k<vn, forms a Steiner triple system, where the a’s, b’s, c’s, and d’s range over all combinations of 0s, 1s, and 2s such that b; +c; +d; =0 (modulo 3) for 1 < j <n, -k.

Verified: yes
Solve time: 1m24s

Solution

Let the point set be $V = {0,1,2}^n$. For $1 \le k \le n$, fix a prefix $(a_1,\dots,a_{k-1}) \in {0,1,2}^{k-1}$ and suffix vectors $b,c,d \in {0,1,2}^{n-k}$ satisfying

$$ b_j + c_j + d_j \equiv 0 \pmod 3 \quad (1 \le j \le n-k). $$

Define three points in $V$ by

$$ x = (a_1,\dots,a_{k-1},0,b), \quad y = (a_1,\dots,a_{k-1},1,c), \quad z = (a_1,\dots,a_{k-1},2,d). $$

Each such triple is a block. Denote the family of all blocks by $\mathcal{B}$.

Each block contains three distinct elements since the $k$-th coordinates are $0,1,2$ respectively.

To prove that $(V,\mathcal{B})$ is a Steiner triple system, it is required to show that every unordered pair of distinct points of $V$ lies in exactly one block.

Let $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$ be distinct elements of $V$. Let $k$ be the least index such that $x_k \ne y_k$. Then $x_j = y_j$ for $1 \le j < k$.

At position $k$, the values $x_k$ and $y_k$ are distinct elements of ${0,1,2}$, so the set ${0,1,2}$ is completed by a unique third element $z_k$ determined by

$$ x_k + y_k + z_k \equiv 0 \pmod 3, $$

so $z_k$ is uniquely determined in ${0,1,2}$.

For coordinates $j > k$, define $z_j$ by

$$ z_j \equiv -x_j - y_j \pmod 3. $$

Then for each $j > k$,

$$ x_j + y_j + z_j \equiv 0 \pmod 3, $$

so the suffix condition of the construction is satisfied.

For $j < k$, the equality $x_j = y_j$ implies that all three points in the block must share the same prefix $(a_1,\dots,a_{k-1})$, so consistency holds with the definition of blocks at level $k$.

Thus there exists a block in $\mathcal{B}$ containing $x$ and $y$.

For uniqueness, the index $k$ is determined solely by the first coordinate at which $x$ and $y$ differ, so no block constructed with a different index $k' \ne k$ can contain both $x$ and $y$, since all blocks at level $k'$ have identical entries in positions $1,\dots,k'-1$ and distinct entries only at position $k'$. Therefore the constructed block is the only one containing the pair ${x,y}$.

Every block contains exactly three elements and every pair of distinct elements of $V$ lies in exactly one block, so $(V,\mathcal{B})$ is a Steiner triple system.

This completes the proof. ∎