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 "1994 IMO Problems/Problem 1"

(Blanked the page)
(Tag: Blanking)
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
 +
\[ \frac {a_1 + a_2 + ... + a_m}{m} \geq \frac {n + 1}{2}.
 +
\]
  
 +
==Solution==
 +
Let <math>a_1, a_2, \dots a_m</math> satisfy the given conditions. We will prove that for all <math>j, 1 \le j \le m,</math>
 +
 +
<cmath>a_j+a_{m-j+1} \ge n+1</cmath>
 +
 +
WLOG, let <math>a_1 < a_2 < \dots < a_m</math>. Assume that for some <math>j, 1 \le j \le m,</math>
 +
 +
<cmath> a_j + a_{m-j+1} \le n</cmath>
 +
 +
This implies, for each <math>i, 1 \le i \le j,</math>
 +
<cmath> a_i + a_{m-j+1} \le n </cmath>
 +
because <math>a_i \le a_j</math>
 +
 +
For each of these values of i, we must have <math>a_i + a_{m-j+1} = a_{k_i}</math> such that <math>a_{k_i}</math> is a member of the sequence for each <math>i</math>. Because <math>a_i > 0, a_{k_i} > a_{m-j+1}</math>.
 +
Combining all of our conditions we have that each of <math>k_i</math> must be distinct integers such that
 +
<cmath>m-j+1 < k_i \le m</cmath>
 +
 +
However, there are <math>j</math> distinct <math>k_i</math>, but only <math>j-1</math> integers satisfying the above inequality, so we have a contradiction. Our assumption that <math>a_j + a_{m-j+1} \le n</math> was false, so <math>a_j + a_{m-j+1} \ge n+1</math> for all <math>j</math> such that <math>1 \le j \le m</math> Summing these inequalities together for <math>1 \le j \le m</math> gives
 +
<cmath> 2(a_1+a_2+ \dots a_m) \ge m(n+1) </cmath>
 +
which rearranges to
 +
<cmath> \frac{a_1+a_2+ \dots a_m}{m} \ge \frac{n+1}{2} </cmath>

Revision as of 22:39, 9 April 2021

Let $m$ and $n$ be two positive integers. Let $a_1$, $a_2$, $\ldots$, $a_m$ be $m$ different numbers from the set $\{1, 2,\ldots, n\}$ such that for any two indices $i$ and $j$ with $1\leq i \leq j \leq m$ and $a_i + a_j \leq n$, there exists an index $k$ such that $a_i + a_j = a_k$. Show that \[ \frac {a_1 + a_2 + ... + a_m}{m} \geq \frac {n + 1}{2}. \]

Solution

Let $a_1, a_2, \dots a_m$ satisfy the given conditions. We will prove that for all $j, 1 \le j \le m,$

\[a_j+a_{m-j+1} \ge n+1\]

WLOG, let $a_1 < a_2 < \dots < a_m$. Assume that for some $j, 1 \le j \le m,$

\[a_j + a_{m-j+1} \le n\]

This implies, for each $i, 1 \le i \le j,$ \[a_i + a_{m-j+1} \le n\] because $a_i \le a_j$

For each of these values of i, we must have $a_i + a_{m-j+1} = a_{k_i}$ such that $a_{k_i}$ is a member of the sequence for each $i$. Because $a_i > 0, a_{k_i} > a_{m-j+1}$. Combining all of our conditions we have that each of $k_i$ must be distinct integers such that \[m-j+1 < k_i \le m\]

However, there are $j$ distinct $k_i$, but only $j-1$ integers satisfying the above inequality, so we have a contradiction. Our assumption that $a_j + a_{m-j+1} \le n$ was false, so $a_j + a_{m-j+1} \ge n+1$ for all $j$ such that $1 \le j \le m$ Summing these inequalities together for $1 \le j \le m$ gives \[2(a_1+a_2+ \dots a_m) \ge m(n+1)\] which rearranges to \[\frac{a_1+a_2+ \dots a_m}{m} \ge \frac{n+1}{2}\]

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1994_IMO_Problems/Problem_1&oldid=151286"