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)
 
(→‎Solution)
Line 1: Line 1:
 +
==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  

Revision as of 20:41, 7 October 2015

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