Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.