Difference between revisions of "1994 IMO Problems/Problem 1"
Line 1: | Line 1: | ||
Let <math> m</math> and <math> n</math> be two positive integers. Let <math> a_1</math>, <math> a_2</math>, <math> \ldots</math>, <math> a_m</math> be <math> m</math> different numbers from the set <math> \{1, 2,\ldots, n\}</math> such that for any two indices <math> i</math> and <math> j</math> with <math> 1\leq i \leq j \leq m</math> and <math> a_i + a_j \leq n</math>, there exists an index <math> k</math> such that <math> a_i + a_j = a_k</math>. Show that | Let <math> m</math> and <math> n</math> be two positive integers. Let <math> a_1</math>, <math> a_2</math>, <math> \ldots</math>, <math> a_m</math> be <math> m</math> different numbers from the set <math> \{1, 2,\ldots, n\}</math> such that for any two indices <math> i</math> and <math> j</math> with <math> 1\leq i \leq j \leq m</math> and <math> a_i + a_j \leq n</math>, there exists an index <math> k</math> such that <math> a_i + a_j = a_k</math>. Show that | ||
− | + | <math>\frac{a_1+a_2+...+a_m}{m} \le \frac{n+1}{2}</math>. | |
− | |||
==Solution== | ==Solution== |
Revision as of 23:40, 9 April 2021
Let and
be two positive integers. Let
,
,
,
be
different numbers from the set
such that for any two indices
and
with
and
, there exists an index
such that
. Show that
.
Solution
Let satisfy the given conditions. We will prove that for all
WLOG, let . Assume that for some
This implies, for each
because
For each of these values of i, we must have such that
is a member of the sequence for each
. Because
.
Combining all of our conditions we have that each of
must be distinct integers such that
However, there are distinct
, but only
integers satisfying the above inequality, so we have a contradiction. Our assumption that
was false, so
for all
such that
Summing these inequalities together for
gives
which rearranges to