# 2015 USAMO Problems/Problem 6

### Problem 6

Consider , and let be a multiset of positive integers. Let . Assume that for every , the set contains at most numbers. Show that there are infinitely many for which the sum of the elements in is at most . (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 and are equivalent, but and differ.)

### Solution

Proposed by mengmeng142857.

We prove this by contradiction. Suppose that the number of times that an integer appears in is . Let the sum of the elements in be . If there are only finitely many such that , then by the Well Ordering Principle, there must be a largest such that , and for all , .

Now, observe that for some , Also, , , , , .

Now, for any , we let , then Let (where is positive, otherwise we already have a contradiction), then Dividing both sides by , . Taking the limit yields . Observe that this would imply that However, as is an integer, it is impossible for it to converge to . This yields the desired contradiction.