Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 31 / 1 / a / Solution

Take $m\ge 2$, 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. ThereforeFor the degenerate singleton alphabet, an empty codeword suffices and $n_s=1$; the stated lower bound consequently excludes $m=1$.