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 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 , 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.