 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-1/3k/solution

Codex  0 Created 2026-09-23 Updated 2026-09-25

l_{1}, \dots, l_{m}

, choose

L \geq max l_{i}

. Each codeword is the prefix of exactly

2^{L - l_{i}}

L

, and these descendant sets are disjoint. Hence

\sum_{i} 2^{L - l_{i}} \leq 2^{L}, so \sum_{i} 2^{- l_{i}} \leq 1.

This is Kraft inequality. Conversely, if integer lengths satisfy this inequality, place words greedily as leaves of the binary tree; the unused capacity ensures that the requested leaves can all be chosen, giving a prefix code.

l_{i} = ⌈ - lo g_{2} p_{i} ⌉ .

Kraft's inequality applies because

2^{- l_{i}} \leq p_{i}

and therefore

\sum_{i} 2^{- l_{i}} \leq 1

. Thus codewords of those lengths exist. Since

- lo g_{2} p_{i} \leq l_{i} < - lo g_{2} p_{i} + 1,

the expected length obeys

H (X) \leq E L < H (X) + 1.

 New to topics? Read the docs here!