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 "2015 IMO Problems/Problem 1"

(→‎Solution)
(→‎Problem and Solution)
Line 1: Line 1:
 +
==Problem==
 +
We say that a finite set <math>\mathcal{S}</math> in the plane is <i> balanced </i>
 +
if, for any two different points <math>A</math>, <math>B</math> in <math>\mathcal{S}</math>, there is
 +
a point <math>C</math> in <math>\mathcal{S}</math> such that <math>AC=BC</math>. We say that
 +
<math>\mathcal{S}</math> is center-free if for any three points <math>A</math>, <math>B</math>, <math>C</math> in
 +
<math>\mathcal{S}</math>, there is no point <math>P</math> in <math>\mathcal{S}</math> such that
 +
<math>PA=PB=PC</math>.
 +
<ol style="list-style-type: lower-latin;">
 +
  <li> Show that for all integers <math>n\geq 3</math>, there exists a balanced set consisting of <math>n</math> points. </li>
 +
  <li> Determine all integers <math>n\geq 3</math>, such that there exists a balanced centre-free set consisting of <math>n</math> points. </li>
 +
</ol>
 +
 
==Solution==
 
==Solution==
  

Revision as of 20:52, 7 October 2015

Problem

We say that a finite set $\mathcal{S}$ in the plane is balanced if, for any two different points $A$, $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC=BC$. We say that $\mathcal{S}$ is center-free if for any three points $A$, $B$, $C$ in $\mathcal{S}$, there is no point $P$ in $\mathcal{S}$ such that $PA=PB=PC$.

  1. Show that for all integers $n\geq 3$, there exists a balanced set consisting of $n$ points.
  2. Determine all integers $n\geq 3$, such that there exists a balanced centre-free set consisting of $n$ points.

Solution

Part (a): We explicitly construct the sets $\mathcal{S}$. For odd $n$, $\mathcal{S}$ can be taken to be the vertices of regular polygons $P_n$ with $n$ sides: given any two vertices $A$ and $B$, one of the two open half-spaces into which $AB$ divides $P_n$ contains an odd number of $k$ of vertices of $P_n$. The $((k+1)/2)^{th}$ vertex encountered while moving from $A$ to $B$ along the circumcircle of $P_n$ is therefore equidistant from $A$ and $B$.

If $n \geq 4$ is even, choose $m\geq 0$ to be the largest integer such that \[x:=(n-2)(\pi/3)/2^m \geq 2\pi/3.\] Hence $x < 4\pi/3 < 2\pi$. Consider a circle $K$ with centre $O$, and let $A_1, \ldots, A_{n-1}$ be distinct points placed counterclockwise (say) on $K$ such that $\angle A_iOA_{i+1}=\pi/3/2^m$ (for $i=1,\ldots,n-2$). Hence for any line $OA_i$, there is a line $OA_j$ such that $\angle A_iOA_j=\pi/3$ (using the facts that $2\pi > x=\angle A_1OA_{n-1} \geq 2\pi/3$, and $n-1$ odd). Thus $O$, $A_i$ and $A_j$ form an equilateral triangle. In other words, for arbitrary $A_i$, there exists $A_j$ equidistant to $O$ and $A_i$. Also given {\em any} $i,j$ such that $1 \leq i, j \leq n-1$, $O$ is equidistant to $A_i$ and $A_j$. Hence the $n$ points $O, A_1, \ldots, A_{n-1}$ form a balanced set.

Part (b): Note that if $n$ is odd, the set $\mathcal{S}$ of vertices of a regular polygon $P_n$ of $n$ sides forms a balanced set (as above) and a centre-free set (trivially, since the centre of the circumscribing circle of $P_n$ does not belong to $\mathcal{S}$).

For $n$ even, we prove that a balanced, centre free set consisting of $n$ sides does not exist. Assume that $\mathcal{S}=\{A_i: 1\leq i \leq n\}$ is center-free. Pick an arbitrary $A_i \in \mathcal{S}$, and let $n_i$ be the number of distinct non-ordered pairs of points $(A_j,A_k)$ ($j\neq k$) to which $A_i$ is equidistant. Any two such pairs are disjoint (for, if there were two such pairs $(A_r,A_s)$ and $(A_r, A_t)$ with $r, s, t$ distinct, then $A_i$ would be equidistant to $A_r$, $A_s$, and $A_t$, violating the centre-free property). Hence $n_i \leq (n-2)/2$ (we use the fact that $n$ is even here), which means $\sum_i n_i \leq n(n-2)/2 = n(n-1)/2 -n/2$. Hence there are at least $n/2$ non-ordered pairs $(A_j, A_k)$ such that no point in $\mathcal{S}$ is equidistant to $A_j$ and $A_k$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_IMO_Problems/Problem_1&oldid=72400"