Competition problem — Combinatorics

Library / /25 of 65

Combinatorics Difficulty 5.9 AIME, harder Prove it Bulgaria

Problem:
Consider a set $S$ of 2006 points in the plane. A pair $(A, B) \in S \times S$ is called "isolated" if the disk with diameter $A B$ does not contain other points from $S$ . Find the maximum number of "isolated" pairs.

Solution

Solution:
Consider a graph with vertices the given points. Two points form an edge if the corresponding pair of points is "isolated". We first prove that the graph is connected. To do this suppose that it has more than one connected component and choose points $A$ and $B$ from different components such that the distance $A B$ is the least possible. Then the disk with diameter $A B$ does not contain other vertices and therefore $A$ and $B$ are connected by an edge. This contradicts the choice of $A$ and $B$ .

Since a connected graph with 2006 vertices has at least 2005 edges (if the graph is a tree) we conclude that there are at least 2005 "isolated" pairs.

If we take 2006 points on a semicircle such that the distances between consecutive points are equal then "isolated" are only the pairs of neighboring points. Therefore there are 2005 "isolated" pairs.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.