OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 17H / c / Solution

Construct a bipartite graph with left vertices

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

, right vertices

B_{1}, \dots, B_{k}

, and an edge

A_{i} B_{j}

exactly when

A_{i} \cap B_{j} \neq = \emptyset

. For

S \subseteq [k]

, every point of

⋃_{i \in S} A_{i}

lies in some

B_{j}

adjacent to one of those

A_{i}

. Thus

⋃_{i \in S} A_{i} \subseteq ⋃_{j \in N (S)} B_{j} .

Using finite additivity of Lebesgue measure and the equal-volume hypotheses,

\frac{∣ S ∣}{k} = vol (⋃_{i \in S} A_{i}) \leq vol (⋃_{j \in N (S)} B_{j}) = \frac{∣ N ( S ) ∣}{k} .

Hence

∣ N (S) ∣ \geq ∣ S ∣

for every

S

. The Hall marriage theorem supplies a perfect matching, which has the form

A_{i} B_{σ (i)}

for a permutation

σ

of

[k]

. Every matched edge means precisely that

A_{i} \cap B_{σ (i)} \neq = \emptyset

.

Solved by gpt-5.6-sol high.

 Ancestors (11)