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

Difference between revisions of "1989 IMO Problems/Problem 3"

(Created page with "Determine all integers <math>n>1</math> such that <cmath>\dfrac{2^n+1}{n^2}</cmath> is also an integer.")
 
Line 1: Line 1:
−
Determine all integers <math>n>1</math> such that
+
==Problem==
−
<cmath>\dfrac{2^n+1}{n^2}</cmath>
+
Let <math> n</math> and <math> k</math> be positive integers and let <math> S</math> be a set of <math> n</math> points in the plane such that
−
is also an integer.
+
 
 +
i.) no three points of <math> S</math> are collinear, and
 +
 
 +
ii.) for every point <math> P</math> of <math> S</math> there are at least <math> k</math> points of <math> S</math> equidistant from <math> P.</math>
 +
 
 +
Prove that:
 +
\[ k < \frac {1}{2} + \sqrt {2 \cdot n}
 +
\]
 +
 
 +
==Solution 1==
 +
Let <math>\{A_i\}_{i=1}^n</math> be our set of points. We count the pairs <math>(A_i,\{A_j,A_\ell\}),\ i\ne j\ne \ell\ne i</math> such that <math>A_iA_j=A_iA_\ell</math>. There are <math>n</math> choices for <math>A_i</math>, and for each <math>A_i</math> there are <math>\ge\frac{k(k-1)}2</math> choices for <math>\{A_j,A_\ell\}</math>, so the number of such pairs is <math>\ge\frac{nk(k-1)}2</math>. On the other hand, there are <math>\frac{n(n-1)}2</math> choices for <math>\{A_j,A_\ell\}</math>, and for each <math>\{A_j,A_\ell\}</math> there are at most two choices for <math>A_i</math> (because we can't have <math>\ge 3</math> points on the perpendicular bisector of <math>A_jA_\ell</math>). This means that the number of pairs is <math>\le n(n-1)</math>. We have thus found <math>n(n-1)\ge\frac{nk(k-1)}2\Rightarrow 2(n-1)\ge k(k-1)\ (*)</math>. If <math>k\ge \sqrt{2n}+\frac 12</math>, then <math>k(k-1)\ge 2n-\frac 14>2n-2</math>, contradicting the last inequality in <math>(*)</math>, so we're done.
 +
 
 +
This solution was posted and copyrighted by grobber. The original thread for this problem can be found here: [https://aops.com/community/p372313]
 +
 
 +
==Solution 2==
 +
So obvious simplification and the fact that <math>n</math> is an integer gives that what we want is <math>n\ge\dbinom{k}{2}+1</math>
 +
Now for each point, draw a circle around it that contains at least <math>k</math> points in <math>S</math>.
 +
For any point <math>P</math> in <math>S</math>, let <math>d_P</math> be the number of circles it's on.
 +
For any point <math>O</math> in <math>S</math>, let <math>f_O</math> be the number of points on the defined circle with center <math>O</math>, so <math>f_O\ge k</math> for all <math>O</math>. Since the function <math>\dbinom{x}{2}</math> is increasing for <math>x\ge 1</math> an integer, <math>\dbinom{f_O}{2}\ge \dbinom{k}{2}</math> for all <math>O</math>. So <math>E(\dbinom{f}{2})\ge \dbinom{k}{2}</math>.
 +
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), <math>\sum_{O\in S}\dbinom{f_O}{2}\le 2\dbinom{n}{2}</math>, since the left side counts the number of point-pairs that share a circle (with possible circle multiplicity) in <math>P</math> while the right side upper-bounds the number of point-pairs that can share a circle (with possible circle multiplicity). So now <math>\dbinom{k}{2}\le E(\dbinom{f}{2})\le (2/n)((n-1)(n)/2)=n-1</math>, which is what we want.
 +
 
 +
This solution was posted and copyrighted by antimonyarsenide. The original thread for this problem can be found here: [https://aops.com/community/p2751749]
 +
 
 +
== See Also == {{IMO box|year=1989|num-b=2|num-a=4}}

Revision as of 11:55, 30 January 2021

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=144063"