Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/iii/paper-109/2/a/solution
Past exam of the mathematics course of the University of Cambridge 2018 iii Paper 109 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Encode each point by a partial binary sequence of length : coordinate is fixed to zero if , fixed to one if , and unrestricted otherwise. Disjointness makes these prescriptions consistent. Let be the number of fixed coordinates, equivalently the number of pairs containing , and let be the set of complete sequences consistent with them. Then .
The separating family of disjoint set pairs ensures that and are disjoint whenever : one coordinate prescribes opposite bits. Counting the sequences in these disjoint subcubes gives the disjoint subcube packing inequalitySince is a convex function, Jensen inequality impliesTaking logarithms yields . Therefore, for ,The PDF omits the qualification . For , it follows from feasibility: separation requires positive total incidence, so the stated incidence bound cannot hold with . For , separation is vacuous, and makes the printed quotient undefined; the intended parameter range is .
New to topics? Read the docs here!