Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 2 / 12H / b

Equiprobability gives $H={\log }_{2}m$.

For $m=2^b$, assign every outcome one of the $b$-bit words. This complete fixed-length prefix code has expected length $b$ and meets the information entropy lower bound.

If two lengths differed by at least two, replacing two deepest sibling leaves by their parent and splitting a shallower leaf lowers total length, contradicting optimality. Thus lengths are $b=\lfloor {\log }_{2}m\rfloor$ and $b+1$. Kraft equality gives $n_b=2^{b+1}-m$ and $n_{b+1}=2m-2^{b+1}$, hence