Problem: Fix $0 < \lambda < 1$, and let $A$ be a multiset of positive integers.
Let $A_n = \{a\in A: a\leq n\}$.
Assume that for every $n \in \NN$, the multiset $A_n$ contains at most $n\lambda$ numbers.
Show that there are infinitely many $n\in\NN$ for
which the sum of the elements in $A_n$ is at most $\frac{n(n+1)}{2}\lambda$.

\end{enumerate}

Solution: For brevity, $\#S$ denotes $|S|$.
Let $x_n = n\lambda - \#A_n \ge 0$.
We now proceed by contradiction by assuming
the conclusion fails for $n$ large enough; that is,
\begin{align*}
  \frac{n(n+1)}{2}\lambda
  &< \sum_{a \in A_n} a \\
  &= 1(\#A_1-\#A_0)
  + 2(\#A_2 - \#A_1)
  + \dots + n(\#A_n - \#A_{n-1}) \\
  &= n \# A_n - (\# A_1 + \dots + \# A_{n-1}) \\
  &= n(n \lambda - x_n) - \left[ (\lambda - x_1)
    + (2\lambda - x_2) + \dots + ((n-1)\lambda - x_{n-1}) \right] \\
  &= \frac{n(n+1)}{2} \lambda - n x_n
  + (x_1 + \dots + x_{n-1}).
\end{align*}
This means that for all sufficiently large $n$, say $n \ge N_0$, we have
\[ x_{n} < \frac{x_1 + \dots + x_{n-1}}{n}
  \qquad \forall n \ge N_0. \]
In particular, each $x_n$ is the less
than the average of all preceding terms.
Intuitively this means $x_n$ should become close to each other,
since they are also nonnegative.

However, we have a second condition we haven't used yet:
the ``integer'' condition implies
\[
  \left\lvert x_{n+1} - x_n \right\rvert
  = \left\lvert \lambda - \#\{n \in A \} \right\rvert
  > \eps
\]
for some fixed $\eps > 0$,
namely $\eps = \min \left\{ \lambda, 1 - \lambda \right\}$.
Using the fact that consecutive terms differ by some fixed $\eps$,
we will derive a contradiction.

If we let $M$ be the average of $x_1$, \dots, $x_{N_0}$,
then we ought to have
\[ x_n < M \qquad \forall n > N_0. \]
Hence for $n > N_0$ we have $x_n + x_{n+1} < 2M - \eps$,
and so for large enough $n$ the average
must drop to just above $M - \half \eps$.
Thus for some large $N_1 > N_0$, we will have
\[ x_n < M - \frac13 \eps \qquad \forall n > N_1. \]
If we repeat this argument then with a large $N_2 > N_1$, we obtain
\[ x_n < M - \frac23 \eps \qquad \forall n > N_2 \]
and so on and so forth.
This is a clear contradiction.

\begin{remark*}
Note that if $A = \{2,2,3,4,5,\dots\}$ and $\lambda = 1$ then contradiction.
So the condition that $0 < \lambda < 1$ cannot be dropped,
and (by scaling) neither can the condition that $A \subseteq \ZZ$.
\end{remark*}

\begin{remark*}
  [Suggested by Zhao Ting-wei]
  Despite the relation
  \[ x_{n} < \frac{x_1 + \dots + x_{n-1}}{n}
    \qquad \forall n \ge N_0 \]
  implying that $x_n$ is bounded,
  it does not alone imply that $x_n$ converges, not even to some nonzero value.
  Zhao Ting-Wei showed me that one can have a sequence which is zero
  ``every so often'' yet where the average is nonzero.

  A counterexample is given explicitly by
  \[
    x_n
    = \begin{cases}
      1000 & n = 1 \\
      0 & n \text{ is a power of $10$} \\
      1 + \frac 1n & \text{otherwise}
    \end{cases}
  \]
  which does not have a limit.
  For completeness, let's check this ---
  let $H_n$ denote the $n$'th harmonic number, and compute
  \begin{align*}
    \sum_1^{n-1} x_n
    &= 1000 + (n-1) + H_{n-1} - \sum_{k=1}^{\left\lfloor \log_{10} n \right\rfloor} \left( 1 + \frac{1}{10^k} \right) \\
    &> n + 999 + H_{n-1} - \log_{10} n - \left( 1 + \frac{1}{10} + \dots \right) \\
    &> n + 997 + H_{n-1} - \log_{10} n > n + 1
  \end{align*}
  so $1 + \frac 1n < \frac 1n \sum_1^{n-1} x_n$ as needed.
\end{remark*}