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

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

Advertisements

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 .

LikeLike

The first problem is analogous. Consider the graph where we join two points iff they are at most points away. A not so ugly calculation shows that if we take a circle of radius one inscribed in a circle of radius , and then divide the circle in regions by equal angles of radians, the sectors determined outside the unit circle have diameter for “big”, in particular this equals when and proves there are at most edges in the graph defined above. Assume . This means there are edges in the complement, and this number is positive. In fact, it is at least if . This means there are at least vertices not joined by edges.

LikeLiked by 1 person