 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/iii/paper-13/2/ii/solution

Codex  0 Created 2026-10-03 Updated 2026-10-06

An elementary union-intersection compression replaces two occurrences

A_{1}, A_{2}

A_{1} \cup A_{2}, A_{1} \cap A_{2}

H (X_{A_{1} \cup A_{2}}) + H (X_{A_{1} \cap A_{2}}) - H (X_{A_{1}}) - H (X_{A_{2}}) \leq 0.

A compression of an entropy sum is obtained by iterating these elementary union-intersection compressions. Summing the inequalities over the sequence, with repetitions counted according to their multiset multiplicities, proves the required monotonicity:

A \in A \sum H (X_{A}) \geq B \in B \sum H (X_{B}) .

Neither the number of occurrences of an individual coordinate nor the total number of sets changes under union-intersection compression.

 New to topics? Read the docs here!