Combinatoral geometric inequality from IMO 1989

A beautiful application of double counting in combinatorial geometry

The Problem

Here’s a classic IMO 1989 problem that showcases the power of combinatorial reasoning in geometry:

Problem: Let $n$ and $k$ be positive integers and let $S$ be a set of $n$ points in the plane such that:

1. no three points of $S$ are collinear, and
2. for every point $P$ of $S$ there are at least $k$ points of $S$ equidistant from $P$.

Prove that $k < \frac{1}{2} + \sqrt{2n}$.

At first glance, this might seem like a daunting geometric problem. However, the key insight lies in recognizing what the constraint is really telling us and how we can leverage the power of double counting.

The Aha! Moment

The breakthrough comes from rearranging the inequality we want to prove. If we manipulate $k < \frac{1}{2} + \sqrt{2n}$, we can rewrite it as:

$$k \, – \, \frac{1}{2} < \sqrt{2n}$$

Squaring both sides (valid since both sides are positive for reasonable values):

$$(k \, – \, \frac{1}{2})^2 < 2n$$

Expanding:

$$k^2 \, -\, k + \frac{1}{4} < 2n$$

Rearranging:

$$n > \frac{k^2 \, -\, k \, + \, \frac{1}{4}}{2} = \frac{(2k\, -\, 1)^2}{8}$$

This is the key insight! The right-hand side is a quadratic expression in $k$, and since this is clearly a counting problem, the appearance of a quadratic suggests that $\binom{k}{2}$ might be involved somewhere.

The Geometric Interpretation

What does condition 2 really mean? For every point $P \in S$, there are at least $k$ other points in $S$ that are all equidistant from $P$. This means these $k$ points lie on a circle centered at $P$.

Now, if we pick any two of these $k$ equidistant points, say $Q$ and $R$, then triangle $PQR$ is isosceles with $PQ = PR$. The point $P$ is the apex of this isosceles triangle.

This observation leads us naturally to a double counting argument involving isosceles triangles.

The Double Counting Argument

Let’s count the number of isosceles triangles in our point set $S$ in two different ways.

Method 1: Choose the Apex First

For each point $P \in S$, we know there are at least $k$ points equidistant from $P$. We can choose any 2 of these $k$ points to form an isosceles triangle with apex at $P$.

Therefore, the number of isosceles triangles with apex at $P$ is at least $\binom{k}{2}$.

Since we have $n$ points total, and each can serve as an apex, we get:

$$\text{Total isosceles triangles} \geq n \cdot \binom{k}{2} = n \cdot \frac{k(k-1)}{2}$$

Method 2: Choose the Base First

Now let’s count differently. Consider any two points $Q, R \in S$. These two points can serve as the base of an isosceles triangle. The apex of such a triangle must be equidistant from both $Q$ and $R$.

The locus of points equidistant from $Q$ and $R$ is the perpendicular bisector of segment $QR$. Since no three points in $S$ are collinear, this perpendicular bisector can contain at most 2 points from $S$ (if it contained 3 or more points from $S$, then those points would be collinear, violating our assumption).

Therefore, for each pair of points ${Q, R}$, there are at most 2 possible apexes, giving us at most 2 isosceles triangles with base $QR$.

Since there are $\binom{n}{2}$ ways to choose the base, we have:

$$\text{Total isosceles triangles} \leq 2 \cdot \binom{n}{2} = 2 \cdot \frac{n(n-1)}{2} = n(n-1)$$

Putting It Together

Combining our two counts:

$$n \cdot \frac{k(k-1)}{2} \leq n(n-1)$$

Dividing both sides by $n$ (since $n > 0$):

$$\frac{k(k-1)}{2} \leq n-1$$

Therefore:

$$k(k-1) \leq 2(n-1) = 2n-2$$

This gives us:

$$k^2 – k \leq 2n – 2$$

Rearranging:

$$k^2 – k + \frac{1}{4} \leq 2n – 2 + \frac{1}{4} = 2n – \frac{7}{4}$$

Since $2n – \frac{7}{4} < 2n$, we have:

$$k^2 – k + \frac{1}{4} < 2n$$

Taking square roots:

$$k – \frac{1}{2} < \sqrt{2n}$$

Therefore:

$$k < \frac{1}{2} + \sqrt{2n}$$.

As Cassius says in Asterix comix,