2015 USAMO Problems/Problem 6

Problem 6

Consider $0<\lambda<1$ , and let $A$ be a multiset of positive integers. Let $A_n=\{a\in A: a\leq n\}$ . Assume that for every $n\in\mathbb{N}$ , the set $A_n$ contains at most $n\lambda$ numbers. Show that there are infinitely many $n\in\mathbb{N}$ for which the sum of the elements in $A_n$ is at most $\frac{n(n+1)}{2}\lambda$ . (A multiset is a set-like collection of elements in which order is ignored, but repetition of elements is allowed and multiplicity of elements is significant. For example, multisets $\{1, 2, 3\}$ and $\{2, 1, 3\}$ are equivalent, but $\{1, 1, 2, 3\}$ and $\{1, 2, 3\}$ differ.)

Solution

Proposed by mengmeng142857.

We prove this by contradiction. Suppose that the number of times that an integer $a$ appears in $A$ is $k_a$ . Let the sum of the elements in $A_n$ be $S_n=\sum_{i=1}^{n}i\cdot k_i$ . If there are only finitely many $n\in\mathbb{N}$ such that $S_n\leq\frac{n(n+1)}{2}\lambda$ , then by the Well Ordering Principle, there must be a largest $m\in\mathbb{N}$ such that $S_m\leq\frac{m(m+1)}{2}\lambda$ , and for all $n>m$ , $S_n>\frac{n(n+1)}{2}\lambda$ .

Now, observe that for some $n>m$ , $\frac{1}{n}\cdot S_{n}+\frac{1}{n(n-1)}\cdot S_{n-1}+\frac{1}{(n-1)(n-2)}\cdot S_{n-2}+...+\frac{1}{2\cdot1}\cdot S_{1} =\sum_{i=1}^{n}k_i \leq n\lambda$ Also, $\frac{S_{n}}{n}>\frac{n+1}{2}\lambda$ , $\frac{S_{n-1}}{n(n-1)}>\frac{1}{2}\lambda$ , $\frac{S_{n-2}}{(n-1)(n-2)}>\frac{1}{2}\lambda$ , $\hdots$ $\frac{S_{m+1}}{(m+2)(m+1)}>\frac{1}{2}\lambda$ , $\frac{S_{m}}{(m+1)m}\leq \frac{1}{2}\lambda$ .

Now, for any $n\in\mathbb{N}$ , we let $\frac{S_n}{(n+1)n}-\frac{1}{2}\lambda=d_n$ , then $\frac{1}{n}\cdot S_n+\sum_{i=1}^{n-1}\frac{S_i}{i(i+1)} =n\lambda+(n+1)\cdot d_n+\sum_{i=m+1}^{n-1}d_i+\sum_{i=1}^{m}d_i \leq n\lambda$ Let $\sum_{i=1}^{m}d_i=-c$ (where $c$ is positive, otherwise we already have a contradiction), then $n\lambda-c< n\lambda+(n+1)\cdot d_n+\sum_{i=m+1}^{n-1}d_i-c =\sum_{i=1}^{n}k_i\leq n\lambda$ Dividing both sides by $n$ , $\lambda-c/n<\frac{\sum_{i=1}^{n}k_i}{n}\leq \lambda$ . Taking the limit yields $\lim_{n\to\infty}{\frac{\sum_{i=1}^{n}k_i}{n}}=\lambda$ . Observe that this would imply that $\lim_{n\to\infty}{k_n} =\lim_{n\to\infty}{\left(\sum_{i=1}^{n}k_i-\sum_{i=1}^{n-1}k_i\right)} =\lim_{n\to\infty}{\left(n\cdot\frac{\sum_{i=1}^{n}k_i}{n}-(n-1)\cdot\frac{\sum_{i=1}^{n-1}k_i}{n-1}\right)} =\lambda$ However, as $k_n$ is an integer, it is impossible for it to converge to $\lambda$ . This yields the desired contradiction.

Page

Toolbox

Search

2015 USAMO Problems/Problem 6

Problem 6

Solution