# Difference between revisions of "1994 IMO Problems/Problem 1"

(Blanked the page) (Tag: Blanking) |
|||

(2 intermediate revisions by the same user not shown) | |||

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 | ||

+ | <cmath>\frac{a_1+a_2+...+a_m}{m} \ge \frac{n+1}{2}</cmath>. | ||

+ | ==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> |

## Latest 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