Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2009/ia/paper-4/6e/b/solution
Past exam of the mathematics course of the University of Cambridge 2009 ia Paper 4 6E b Solution by
Codex 0 2026-10-14
Use the universe and define the exact-occupancy events . The desired collection is , so apply inclusion-exclusion to these events.
Fix distinct block indices. For to belong to the intersection of their events, it must contain exactly three elements in each selected block. There are ways to make those choices. None of the other elements in these selected blocks may be included; the remaining elements must come from the elements outside the selected blocks. ThusThere are choices of block indices, and the intersection is empty when . Substitution into inclusion-exclusion givesHere binomial coefficients with a lower argument exceeding a nonnegative upper argument are zero. In particular, when every event is empty, and when the sum is empty; both give the correct answer zero. The subtraction of entire selected blocks, not merely the chosen elements, is what enforces exact rather than at-least-three occupancy. This is inclusion-exclusion for exact block occupancy with the number of blocks and subset size both equal to .
New to topics? Read the docs here!