 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ia/paper-4/6e/a/solution

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

A_{1}, \dots, A_{k}

∣ ⋃_{i} A_{i} ∣ = \sum_{i} ∣ A_{i} ∣ - \sum_{i < j} ∣ A_{i} \cap A_{j} ∣ + \dots + (- 1)^{k + 1} ∣ A_{1} \cap \dots \cap A_{k} ∣.

For each prime

p ∣ n

, exclude pairs whose two coordinates are divisible by

p

. For a set of distinct prime divisors

p_{1}, \dots, p_{j}

, exactly

n^{2} / (p_{1} \dots p_{j})^{2}

pairs have both coordinates divisible by their product. Inclusion-exclusion therefore gives

∣ Y ∣ = n^{2} p ∣ n \prod (1 - \frac{1}{p ^{2}}) .

 New to topics? Read the docs here!