Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1989 IMO Problems/Problem 3

Problem

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

i.) no three points of $S$ are collinear, and

ii.) for every point $P$ of $S$ there are at least $k$ points of $S$ equidistant from $P.$

Prove that: \[k < \frac {1}{2} + \sqrt {2 \cdot n}\]

Solution 1

Let $\{A_i\}_{i=1}^n$ be our set of points. We count the pairs $(A_i,\{A_j,A_\ell\}),\ i\ne j\ne \ell\ne i$ such that $A_iA_j=A_iA_\ell$. There are $n$ choices for $A_i$, and for each $A_i$ there are $\ge\frac{k(k-1)}2$ choices for $\{A_j,A_\ell\}$, so the number of such pairs is $\ge\frac{nk(k-1)}2$. On the other hand, there are $\frac{n(n-1)}2$ choices for $\{A_j,A_\ell\}$, and for each $\{A_j,A_\ell\}$ there are at most two choices for $A_i$ (because we can't have $\ge 3$ points on the perpendicular bisector of $A_jA_\ell$). This means that the number of pairs is $\le n(n-1)$. We have thus found $n(n-1)\ge\frac{nk(k-1)}2\Rightarrow 2(n-1)\ge k(k-1)\ (*)$. If $k\ge \sqrt{2n}+\frac 12$, then $k(k-1)\ge 2n-\frac 14>2n-2$, contradicting the last inequality in $(*)$, so we're done.

This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [1]

Solution 2

So obvious simplification and the fact that $n$ is an integer gives that what we want is $n\ge\dbinom{k}{2}+1$ Now for each point, draw a circle around it that contains at least $k$ points in $S$. For any point $P$ in $S$, let $d_P$ be the number of circles it's on. For any point $O$ in $S$, let $f_O$ be the number of points on the defined circle with center $O$, so $f_O\ge k$ for all $O$. Since the function $\dbinom{x}{2}$ is increasing for $x\ge 1$ an integer, $\dbinom{f_O}{2}\ge \dbinom{k}{2}$ for all $O$. So $E(\dbinom{f}{2})\ge \dbinom{k}{2}$. But notice that since any pair of two points shares at most 2 circles (otherwise we have 3 circles with centers on their perpendicular bisector, which is not allowed), $\sum_{O\in S}\dbinom{f_O}{2}\le 2\dbinom{n}{2}$, since the left side counts the number of point-pairs that share a circle (with possible circle multiplicity) in $P$ while the right side upper-bounds the number of point-pairs that can share a circle (with possible circle multiplicity). So now $\dbinom{k}{2}\le E(\dbinom{f}{2})\le (2/n)((n-1)(n)/2)=n-1$, which is what we want.

This solution was posted and copyrighted by antimonyarsenide. The original thread for this problem can be found here: [2]

See Also

1989 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1989_IMO_Problems/Problem_3&oldid=144064"