Difference between revisions of "2015 IMO Problems/Problem 1"
(→Problem and Solution) |
m (→See Also) |
||
(7 intermediate revisions by 3 users not shown) | |||
Line 3: | Line 3: | ||
if, for any two different points <math>A</math>, <math>B</math> in <math>\mathcal{S}</math>, there is | 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 | a point <math>C</math> in <math>\mathcal{S}</math> such that <math>AC=BC</math>. We say that | ||
− | <math>\mathcal{S}</math> is | + | <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>\mathcal{S}</math>, there is no point <math>P</math> in <math>\mathcal{S}</math> such that | ||
<math>PA=PB=PC</math>. | <math>PA=PB=PC</math>. | ||
<ol style="list-style-type: lower-latin;"> | <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> 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> | + | <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> | + | </ol> |
==Solution== | ==Solution== | ||
Line 34: | 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 | + | <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 44: | 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> | ||
− | + | points does <b>not</b> exist. Assume that | |
− | <math>\mathcal{S}=\{A_i: 1\leq i \leq n\}</math> is | + | <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 57: | 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 08:14, 19 July 2016
Problem
We say that a finite set in the plane is balanced
if, for any two different points
,
in
, there is
a point
in
such that
. We say that
is centre-free if for any three points
,
,
in
, there is no point
in
such that
.
- Show that for all integers
, there exists a balanced set consisting of
points.
- Determine all integers
for which there exists a balanced centre-free set consisting of
points.
Solution
Part (a): We explicitly construct the sets . For
odd
,
can be taken to be the vertices of
regular polygons
with
sides: given any two vertices
and
, one of the two open half-spaces into
which
divides
contains an odd number of
of vertices of
. The
vertex encountered while moving from
to
along the circumcircle of
is therefore equidistant from
and
.
If is even, choose
to be the largest
integer such that
Hence
. Consider a circle
with centre
, and let
be distinct points placed counterclockwise
(say) on
such that
(for
). Hence for any line
, there is a line
such that
(using the facts that
, and
odd). Thus
,
and
form an equilateral triangle. In other words, for
arbitrary
, there exists
equidistant to
and
. Also given any
such that
,
is equidistant to
and
. Hence
the
points
form a balanced set.
Part (b): Note that if is odd, the set
of
vertices of a regular polygon
of
sides forms a balanced set
(as above) and a centre-free set (trivially, since the centre of the
circumscribing circle of
does not belong to
).
For even, we prove that a balanced, centre free set consisting of
points does not exist. Assume that
is centre-free. Pick an
arbitrary
, and let
be the number of
distinct non-ordered pairs of points
(
) to
which
is equidistant. Any
two such pairs are disjoint (for, if there were two such pairs
and
with
distinct, then
would be
equidistant to
,
, and
, violating the centre-free
property). Hence
(we use the fact that
is even here), which means
. Hence there are at least
non-ordered pairs
such that no point in
is equidistant to
and
.
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 |