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

Relabel the symbols so $p_1\ge \cdots \ge p_m$ and assign all finite binary strings in nondecreasing length order, beginning with the empty string. The $i$th string has lengthSince $1\ge {\sum }_{j=1}^i{p}_j\ge i{p}_i$,Thus the optimal one-to-one binary code satisfies