# Disperse subsets

Suppose we’re given $N$ points in the plane that are all more than one unit apart in distance. Prove there is a subset of size at least $N/7$ whose points are more than $\sqrt 3$ units apart. Try to avoid induction.

Suppose now that we have $N$ points in the plane all at least one unit apart in distance. Prove there are at most $3N$ pairs of points at exactly one unit of distance apart.

Advertisements

## 2 thoughts on “Disperse subsets”

1. For the second problem, consider the graph obtained by joining two points iff they are at distance exactly one. Then each vertex has at most six neighbours: if there are seven, the pigeonhole principle gives two inside the sixth of a segment of the circle, and these will be less than one unit apart. The handshaking lemma gives twice the number of edges is at most six times the number of vertices, or $e\leqslant 3N$.

Like

2. The first problem is analogous. Consider the graph where we join two points iff they are at most $\sqrt 3$ points away. A not so ugly calculation shows that if we take a circle of radius one inscribed in a circle of radius $\sqrt 3$, and then divide the circle in $n$ regions by equal angles of $2 \pi/n$ radians, the sectors determined outside the unit circle have diameter $4-2\sqrt 3 \cos (2\pi /n)$ for $n$ “big”, in particular this equals $1$ when $n=12$ and proves there are at most $6N$ edges in the graph defined above. Assume $N\geqslant 14$. This means there are $\binom{N}{2}- 6N$ edges in the complement, and this number is positive. In fact, it is at least $2N/7$ if $N\geqslant 14$. This means there are at least $N/7$ vertices not joined by edges.

Liked by 1 person