 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-168/3/iv/solution

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

Assume first that no two members of the uniform set family

A \subseteq [n]^{(k)}

meet in exactly one point. Fix

A_{0} \in A

. Since

A

B \in A

then contains at least two elements of

A_{0}

. Consequently

∣ A ∣ \leq (2 k) (k - 2 n - 2) = O (n^{k - 2}) = o ((k - 1 n - 1)) .

This proves the stated dichotomy.

If the small alternative holds, then for sufficiently large

n

any fixed

i

has all but at most

ε (k - 1 n - 1)

members of

A

containing it. Otherwise choose

A, B \in A

with

A \cap B = {i}

. Every

C \in A

not containing

i

must meet both

A ∖ {i}

and

B ∖ {i}

, so

∣ {C \in A : i \in / C} ∣ \leq (k - 1)^{2} (k - 2 n - 2) = o ((k - 1 n - 1)) .

For sufficiently large

n

this is at most

ε (k - 1 n - 1)

, as required.

 New to topics? Read the docs here!