Difference between revisions of "1989 IMO Problems/Problem 3"
Line 7: | Line 7: | ||
Prove that: | Prove that: | ||
− | + | <cmath> k < \frac {1}{2} + \sqrt {2 \cdot n} </cmath> | |
− | |||
==Solution 1== | ==Solution 1== |
Latest revision as of 11:56, 30 January 2021
Contents
Problem
Let and
be positive integers and let
be a set of
points in the plane such that
i.) no three points of are collinear, and
ii.) for every point of
there are at least
points of
equidistant from
Prove that:
Solution 1
Let be our set of points. We count the pairs
such that
. There are
choices for
, and for each
there are
choices for
, so the number of such pairs is
. On the other hand, there are
choices for
, and for each
there are at most two choices for
(because we can't have
points on the perpendicular bisector of
). This means that the number of pairs is
. We have thus found
. If
, then
, 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 is an integer gives that what we want is
Now for each point, draw a circle around it that contains at least
points in
.
For any point
in
, let
be the number of circles it's on.
For any point
in
, let
be the number of points on the defined circle with center
, so
for all
. Since the function
is increasing for
an integer,
for all
. So
.
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),
, since the left side counts the number of point-pairs that share a circle (with possible circle multiplicity) in
while the right side upper-bounds the number of point-pairs that can share a circle (with possible circle multiplicity). So now
, 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 |