Let $n$ and $k$ be positive integers. Given $n$ closed discs in the plane such that no matter how we choose $k + 1$ of them, there are always two of the chosen discs that have no common point. Prove that the $n$ discs can be partitioned into at most $10k$ classes such that any two discs in the same class have no common point.
Problem
Source: 2020 Kürschák Competition P1
Tags: combinatorics, combinatorical geometry
Ti-Ci
18.09.2021 16:18
Have no ideas... Any hints, please?
NTstrucker
18.09.2021 19:43
Use strong induction on $n$.
Hint 2If a disc $\mathcal{D}$ intersects at most $10k-1$ discs, we can delete it and use induction hypothesis. A nice choice of $\mathcal{D}$ would be the minimal disc.
Hint 3Use a common trick in real analysis (e.g. Vitali covering lemma): expand $\mathcal{D}=\mathcal{B}(O,r)$ to $\mathcal{D'}=\mathcal{B}(O,3r)$.
Prove that all circles that intersect $\mathcal{D}$ lie completely in $\mathcal{D'}$. Now consider areas yields that at most $9k-1$ circles intersect $\mathcal{D}$.
SerdarBozdag
23.09.2021 17:06
I do not know what lemma is in hint 3. Is there an elementary solution?