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
Disperse subsets

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s