Problem:
Consider 0<λ<1, and let A be a multiset of positive integers. Let An={a∈A:a≤n}. Assume that for every n∈N, the set An contains at most nλ numbers. Show that there are infinitely many n∈N for which the sum of the elements in An is at most 2n(n+1)λ. (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:
Set bn=∣An∣,an=nλ−An≥0. There are bi−bi−1 elements equal to i. Therefore the sum of elements in An is
i=1∑ni(bi−bi−1)=nbn−i=1∑nbi
Now bn=nλ−an, so the sum of elements in An may be written as
Σn=λ2n(n+1)−nan+i=1∑n−1ai
Assume, by way of contradiction, that for all n≥n0, the sum of elements in An is greater than λ2n(n+1). Then
nan<an−1+an−2+…+a1
so
an<nan−1+an−2+…+a1≤nMn⋅(n−1)(4)
where Mn= max{ a1, a2,..., an−1}. We deduce that an<n(n−1)Mn,
so Mn+1=Mn=M, where M=Mn0.
Let {x} denote the fractional part of x; i.e., {x}=x−⌊x⌋. We note that ak+1−ak=λ, so (M−ak)−M−ak+1)=λ. We claim that
(M−ak)+(M−ak+1)≥min(λ,1−λ)(5)
To see this, we first note that M−ak≥0 and M−ak+1≥0. If either M−ak≥1 or M−ak+1≥1, then we are done. Assume that 0<M−ak,M−ak+1<1. Then −1<(M−ak)−(M−ak+1)<1, so either (M−ak)−(M−ak+1)=λ−1 or (M−ak)− (M−ak+1)=λ. In the former case, we get M−ak+1>1−λ, and in the latter case we get M−ak>λ. In either case, (5) follows.
We deduce from (5) that ak+ak+1≤2M−μ, where μ=min(λ,1−λ). From this and (4), we see that
an≤M−2μ(6)
for n≥n1=n0+1.
Let δ=μ/3. We will use induction to prove that for any integer k≥1 and n≥nk,
an≤M−kδ(7)
We have already proved the base case. Assume that (7) is true for a given fixed k. Using (6), we see that ak+ak+1≤2M−2kδ−μ=2M−(2k+3)δ. (Note that δ≤1/6, so min(δ,1−δ)=δ.) Now if we take n>(2k+3)nk, we deduce that
an≤nnkM+(n−nk)(M−(k+23)δ)≤M−(k+1)δ
Statement (7) then follows by induction. However, it then follows that an<0 when k>M/δ, and this is a contradiction.
The problems on this page are the property of the MAA's American Mathematics Competitions