Given $3n+1$ points such that any $4$ of them contain a pair at distance at most $1$, then $n+1$ fit in a disc of radius $1$.

73 Views Asked by At

I've been working through some pigeonhole principle problems and have some issues with this one. While in general working out more examples gives better intuition/toolkit, I feel like pigeonhole is still rather hit or miss, especially in the case of geometry for me.

The question is as follows: we have $3n+1$ points given in the plane, with the added condition that for any $4$ of these points there are $2$ of them at distance at most $1$. We need to show that $n+1$ fit in a disc of radius $1$.

Any general tips for tackling these types of problems are much appreciated as well.