 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ii/paper-1/3i/b/iii/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

The binary entropy is

H = \sum_{k = 1}^{4} p_{k} lo g_{2} \frac{1}{p _{k}} \approx 0.1 (3.32) + 0.2 (2.32) + 0.3 (1.74) + 0.4 (1.32) = 1.846.

H \leq \overline{ℓ} < H + 1

for the standard Shannon construction, while every prefix code obeys the lower bound. Numerically,

1.846 \leq 2.4 < 2.846, 1.846 \leq 1.9 < 2.846.

Thus both codes satisfy the theorem, with the Huffman code closer to the entropy lower bound.

 New to topics? Read the docs here!