# probabilistic method- 2 colouring of points in the plane

I'm hoping some of you might be able to help me with this question and hint me twords a solution using the probabilistic method.

Let P be a set of at most $2^{k/3}$ points in the plane. Prove that there exists a coloring of P with two colors such that in every open disc that contains at least k points both colors are present.

I've tried bounding the number of discs with $\binom{n}{3}$ for n the number of points, but i've failed to find a compelling argument.

thanks

-

The claim is false for $k=1$, so I'll assume you forgot to state the assumption $k\gt1$.

At Number of point subsets that can be covered by a disk, it's shown that for $n$ points, no three of which are colinear and no four of which are concyclic, there are exactly $(n^2+5)n/6$ different subsets coverable with closed disks. It seems that the argument also works for open disks and that points being colinear or concyclic can only reduce the number of different subsets, so $(n^2+5)n/6$ is an upper bound.

With $n\le2^{k/3}$, there are thus at most $(2^{2k/3}+5)2^{k/3}/6$ different disks, and for $k\gt1$ this is less than $2^{k-1}$. The expected number of monochromatic disks in a random colouring with uniformly and independently distributed colours is $2^{-(k-1)}$ times the number of disks. Since this is less than $1$, there must be a colouring without monochromatic disks.

-