MathDB

discs that CAN be partitioned into at most 10k classes

Source: 2020 Kürschák Competition P1

April 10, 2021

combinatoricscombinatorical geometry

Problem Statement

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.