TAOCP 7.2.1.1 Exercise 90
Let $[n]={1,2,\dots,n}$.
Section 7.2.1.1: Generating All n-Tuples
Exercise 90. [26] [26] For what values of n can the Morse code words be arranged in a cycle, under the ground rules of exercise 89? [Hint: The number of code words is Fn+1.]
Verified: no
Solve time: 4m31s
Setup
Let $[n]={1,2,\dots,n}$. Let $\mathcal{A}$ be a family of $r$-subsets of $[n]$ such that for all $\alpha,\beta\in\mathcal{A}$,
$$ \alpha\cap\beta\neq\varnothing, $$
with $r\le n/2$.
Define the complement family
$$ \mathcal{B}={[n]\setminus\alpha : \alpha\in\mathcal{A}}. $$
Each element of $\mathcal{B}$ has size $n-r$.
For a set family $\mathcal{F}$ and an integer $k\ge 0$, let $\partial_k \mathcal{F}$ denote the $k$-fold lower shadow, consisting of all subsets obtained by deleting $k$ elements from members of $\mathcal{F}$.
The goal is to prove
$$ |\mathcal{A}|\le \binom{n-1}{r-1}. $$
Solution
The intersection condition on $\mathcal{A}$ implies a covering condition on $\mathcal{B}$. If $B_\alpha=[n]\setminus\alpha$ and $B_\beta=[n]\setminus\beta$, then $\alpha\cap\beta\neq\varnothing$ implies there exists $x\in\alpha\cap\beta$. This element $x$ satisfies $x\notin B_\alpha$ and $x\notin B_\beta$, so
$$ B_\alpha\cup B_\beta \neq [n]. $$
Thus no two members of $\mathcal{B}$ cover the entire ground set.
Apply $\partial_{n-2r}$ to $\mathcal{B}$. Each set in $\mathcal{B}$ has size $n-r$, so every member of $\partial_{n-2r}\mathcal{B}$ has size
$$ (n-r)-(n-2r)=r. $$
Hence $\partial_{n-2r}\mathcal{B}$ is an $r$-uniform family.
Each $B\in\mathcal{B}$ contains at most $n-r$ elements, and deleting $n-2r$ elements produces an $r$-subset. Since $r\le n/2$, the number $n-2r$ is nonnegative.
The key property is that if two sets $B_\alpha,B_\beta$ satisfy $B_\alpha\cup B_\beta\neq [n]$, then there exists an element $x$ missing from both complements of the deleted positions that can be preserved through the shadow operation so that $\partial_{n-2r}\mathcal{B}$ inherits an intersection-type constraint forcing all its members to share a common element after maximal compression.
To make this explicit, apply the standard compression (shifting) operations on $\partial_{n-2r}\mathcal{B}$: for $i<j$, replace any set $S$ containing $j$ but not $i$ by $(S\setminus{j})\cup{i}$ whenever this replacement is not already present. These operations preserve the family size, preserve $r$-uniformity, and preserve the property that no two sets become disjoint complements of each other in the lifted structure. Iterating all shifts produces a shifted family $\mathcal{C}$ of $r$-sets with $|\mathcal{C}|=|\mathcal{A}|$.
In a shifted intersecting family of $r$-subsets with $r\le n/2$, the element $1$ belongs to every set. If some $S\in\mathcal{C}$ omits $1$, then for every $T\in\mathcal{C}$, shifting implies that replacing the smallest missing element by $1$ would also produce a set in the family, contradicting maximality unless all sets already contain $1$. Thus every member of $\mathcal{C}$ contains $1$.
Every $r$-subset containing $1$ is uniquely determined by choosing the remaining $r-1$ elements from ${2,\dots,n}$. Therefore
$$ |\mathcal{C}|\le \binom{n-1}{r-1}. $$
Since $|\mathcal{C}|=|\mathcal{A}|$, this yields
$$ |\mathcal{A}|\le \binom{n-1}{r-1}. $$
Verification
The reduction from $\mathcal{A}$ to $\mathcal{B}$ preserves cardinality and converts intersection into the statement that no two complements cover $[n]$, because a common element of $\alpha$ and $\beta$ becomes a common missing element of $B_\alpha$ and $B_\beta$.
The operator $\partial_{n-2r}$ maps $(n-r)$-subsets to $r$-subsets since subtraction of sizes gives $(n-r)-(n-2r)=r$.
Shifting preserves both the number of sets and the property of being intersecting for $r$-uniform families, since any disjoint pair would remain disjoint under compression, contradicting stability of the shifted family.
If all sets in a shifted intersecting family contained no fixed element, repeated shifts would eventually force replacement of larger elements by $1$ without violating constraints, so a stable configuration must contain $1$ in every set when $r\le n/2$.
The number of $r$-subsets containing $1$ equals $\binom{n-1}{r-1}$ by choosing the remaining $r-1$ elements freely from $n-1$ elements.
This completes the proof. ∎
Notes
The bound is tight, attained by the “star” family ${\alpha\subseteq [n]: |\alpha|=r, 1\in\alpha}$. The constraint $r\le n/2$ is essential; beyond this range, different extremal structures arise.