Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 224 / 4 / c / i / Solution

For any fixed threshold $R$, minimizing the excess-length probability means assigning the available strings shorter than $R$ to the most probable symbols. Repeating this exchange argument simultaneously for every threshold orders symbols by decreasing probability and assigns binary strings from shortest to longest. There are $2^{\ell }$ words of length $\ell$, so the $k$th word in shortlex order has lengthThis is the optimal one-to-one binary code.