= Solution
Take $m\ge2$, as required for the lower bound in this part. A binary <Huffman code> has a <full binary tree>: every merge has two children, and all <codewords> are leaves. More generally an optimal <prefix code> for positive-probability symbols cannot have an internal vertex with only one child, since suppressing that vertex shortens its descendant <codewords> and reduces the expected length.
Choose a leaf of maximum depth $s$. Its sibling must also be a leaf, since an internal sibling would have a descendant deeper than $s$. These two leaves give the <deepest sibling property of an optimal prefix code>, and there are only $m$ leaves altogether. Therefore
$$
\boxed{2\le n_s\le m.}
$$
For the degenerate singleton alphabet, an empty <codeword> suffices and $n_s=1$; the stated lower bound consequently excludes $m=1$.
Back to article page
