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"

(Added solution)
 
m (→‎See Also)
 
(9 intermediate revisions by 3 users not shown)
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 <i>centre-free</i> 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> for which there exists a balanced centre-free set consisting of <math>n</math> points. </li>
 +
</ol>
 +
 +
==Solution==
 +
 
<b>Part (a):</b> We explicitly construct the sets <math>\mathcal{S}</math>. For
 
<b>Part (a):</b> We explicitly construct the sets <math>\mathcal{S}</math>. For
 
odd <math>n</math>, <math>\mathcal{S}</math> can be taken to be the vertices of  
 
odd <math>n</math>, <math>\mathcal{S}</math> can be taken to be the vertices of  
Line 20: Line 34:
 
<math>O</math>, <math>A_i</math> and <math>A_j</math> form an equilateral triangle. In other words, for
 
<math>O</math>, <math>A_i</math> and <math>A_j</math> form an equilateral triangle. In other words, for
 
arbitrary <math>A_i</math>, there exists <math>A_j</math> equidistant to
 
arbitrary <math>A_i</math>, there exists <math>A_j</math> equidistant to
−
<math>O</math> and <math>A_i</math>. Also given {\em any} <math>i,j</math> such that
+
<math>O</math> and <math>A_i</math>. Also given <i>any</i> <math>i,j</math> such that
 
<math>1 \leq i, j \leq n-1</math>, <math>O</math> is equidistant to <math>A_i</math> and <math>A_j</math>. Hence
 
<math>1 \leq i, j \leq n-1</math>, <math>O</math> is equidistant to <math>A_i</math> and <math>A_j</math>. Hence
 
the <math>n</math> points <math>O, A_1, \ldots, A_{n-1}</math> form a balanced set.
 
the <math>n</math> points <math>O, A_1, \ldots, A_{n-1}</math> form a balanced set.
Line 30: Line 44:
  
 
For <math>n</math> even, we prove that a balanced, centre free set consisting of <math>n</math>
 
For <math>n</math> even, we prove that a balanced, centre free set consisting of <math>n</math>
−
sides does <b>not</b> exist.  Assume that
+
points does <b>not</b> exist.  Assume that
−
<math>\mathcal{S}=\{A_i: 1\leq i \leq n\}</math> is center-free. Pick an
+
<math>\mathcal{S}=\{A_i: 1\leq i \leq n\}</math> is centre-free. Pick an
 
arbitrary <math>A_i \in \mathcal{S}</math>, and let <math>n_i</math> be the number of
 
arbitrary <math>A_i \in \mathcal{S}</math>, and let <math>n_i</math> be the number of
 
distinct non-ordered pairs of points <math>(A_j,A_k)</math> (<math>j\neq k</math>) to
 
distinct non-ordered pairs of points <math>(A_j,A_k)</math> (<math>j\neq k</math>) to
Line 43: Line 57:
 
<math>n/2</math> non-ordered pairs <math>(A_j, A_k)</math> such that no point in
 
<math>n/2</math> non-ordered pairs <math>(A_j, A_k)</math> such that no point in
 
<math>\mathcal{S}</math> is equidistant to <math>A_j</math> and <math>A_k</math>.
 
<math>\mathcal{S}</math> is equidistant to <math>A_j</math> and <math>A_k</math>.
 +
 +
==See Also==
 +
 +
{{IMO box|year=2015|before=First Problem|num-a=2}}
 +
 +
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 07:14, 19 July 2016

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 centre-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$ for which 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 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$ points does not exist. Assume that $\mathcal{S}=\{A_i: 1\leq i \leq n\}$ is centre-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$.

See Also

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