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.