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"

(→‎See Also)
m (→‎See Also)
Line 62: Line 62:
 
{{IMO box|year=2015|num-b=0|num-a=2}}
 
{{IMO box|year=2015|num-b=0|num-a=2}}
  
−
[[Category:Olympiad Combinatorics Problems lol]]
+
[[Category:Olympiad Combinatorics Problems]]

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
Problem 0 		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=79550"