Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/iii/paper-109/2/a/solution

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 inequality
Since is a convex function, Jensen inequality implies
Taking 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!