 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ii/paper-2/30j/c/solution

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

x_{1 : n}

is shattered by

⋃_{k = 1}^{r} F_{k}

, then all

2^{n}

label vectors belong to the union of the label-vector sets generated by the individual classes. The shattering coefficient of a union and the Sauer-Shelah lemma therefore give

2^{n} \leq \sum_{k = 1}^{r} s (F_{k}, n) \leq r \sum_{j = 0}^{v} (j n) \leq r (n + 1)^{v} .

Taking base-two logarithms yields

n \leq lo g_{2} r + v lo g_{2} (n + 1) .

For

r > 1

, apply the stated elementary bound with

α = lo g_{2} r

and

β = v \geq 3

n \leq 4 v lo g_{2} (2 v) + 2 lo g_{2} r .

r = 1

, the assertion follows directly from

n \leq v

. Taking the largest shattered sample size proves

VC (k = 1 ⋃ r F_{k}) \leq 4 v lo g_{2} (2 v) + 2 lo g_{2} r .

 New to topics? Read the docs here!