MathDB

6

Part of 2015 USAMO

Problems(1)

Funny sequence

Source: 2015 USAMO problem 6

4/29/2015
Consider 0<λ<10<\lambda<1, and let AA be a multiset of positive integers. Let An={a∈A:a≤n}A_n=\{a\in A: a\leq n\}. Assume that for every n∈Nn\in\mathbb{N}, the set AnA_n contains at most nλn\lambda numbers. Show that there are infinitely many n∈Nn\in\mathbb{N} for which the sum of the elements in AnA_n is at most n(n+1)2λ\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}\{1, 2, 3\} and {2,1,3}\{2, 1, 3\} are equivalent, but {1,1,2,3}\{1, 1, 2, 3\} and {1,2,3}\{1, 2, 3\} differ.)
AMCUSA(J)MOUSAMOSequenceSets