 Solution

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

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

For a

q

-ary code with codeword lengths

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

i = 1 \sum m q^{- l_{i}} \leq 1 .

Choose an infinite random

q

-ary string with independent uniform symbols. The event that it begins with codeword

i

q^{- l_{i}}

. For a prefix-free code, these events are disjoint, so their probabilities sum to at most one. This proves necessity.

 New to topics? Read the docs here!