Competition problem — Number theory

Library / /86 of 520

Number theory Difficulty 5.6 AIME, harder Prove it

2. A2 (FRA) ${ }^{\mathrm{IMO} 1}$ Let $m$ and $n$ be positive integers. The set $A=\left\{a_{1}, a_{2}, \ldots, a_{m}\right\}$ is a subset of $\{1,2, \ldots, n\}$ . Whenever $a_{i}+a_{j} \leq n, 1 \leq i \leq j \leq m$ , $a_{i}+a_{j}$ also belongs to $A$ . Prove that
$\frac{a_{1}+a_{2}+\cdots+a_{m}}{m} \geq \frac{n+1}{2} .$

Solution

2. We may assume that $a_{1}>a_{2}>\cdots>a_{m}$ . We claim that for $i=1, \ldots, m$ , $a_{i}+a_{m+1-i} \geq n+1$ . Indeed, otherwise $a_{i}+a_{m+1-i}, \ldots, a_{i}+a_{m-1}, a_{i}+a_{m}$ are $i$ different elements of $A$ greater than $a_{i}$ , which is impossible. Now by adding for $i=1, \ldots, m$ we obtain $2\left(a_{1}+\cdots+a_{m}\right) \geq m(n+1)$ , and the result follows.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.