This doesn't make sense to me. What if you consider x = floor of n*lambda, and let the set be {1,2,3...x}? Its obviously true then

I tried defining some sequences and using convergence, not sure if it worked though. EDIT: Found a complete solution, still working out some details though. Solution. For $i \in \mathbb{N}$, let $x_i$ be the size of the multiset $A_i$, divided by $i.$ Then by the given condition, the sequence $X = \{x_i\}_{i = 1}^{\infty}$ is bounded above by $\lambda.$ To simplify the algebra, we define three new sequences: \begin{align*} Y = \{y_i\}_{i = 1}^{\infty}, \quad y_i &= x_1 + 2x_2 + \cdots + ix_i \\ S = \{s_i\}_{i = 1}^{\infty}, \quad s_i &= \frac{y_i}{i + 1} \\ T = \{t_i\}_{i = 1}^{\infty}, \quad t_i &= \frac{s_i}{i} \end{align*} By convention, we set $x_0 = y_0 = s_0 = 0.$ Now, observe that the number of times an integer $k$ appears in the multiset $A$ is $kx_k - (k - 1)x_{k - 1}$, and these elements contribute a sum of $k\left(kx_k - (k - 1)x_{k - 1}\right)$ to $A.$ Therefore, the sum of the elements of $A_n$ is \begin{align*} \sum\limits_{i = 1}^n i\left(ix_i - (i - 1)x_{i - 1}\right) &= 1\left(x_1 - 0\right) + 2\left(2x_2 - x_1\right) + \cdots + n\left(nx_n - (n - 1)x_{n - 1}\right) \\ &= (1 - 2)x_1 + (4 - 6)x_2 + \cdots + \left(\left(n - 1\right)^2 - n(n - 1)\right)x_{n - 1} + n^2x_n \\ &= -x_1 - 2x_2 - \cdots - (n - 1)x_{n - 1} + n^2x_n \\ &= -y_{n - 1} + n\left(nx_n\right) \\ &= -y_{n - 1} + n\left(y_n - y_{n - 1}\right) \\ &= ny_n - (n + 1)y_{n - 1}. \end{align*} We wish to bound this expression by $\tfrac{n(n + 1)}{2}\lambda$ for infinitely many $n \in \mathbb{N}.$ Upon division by $n(n + 1)$, we see that \[ny_n - (n + 1)y_{n - 1} \le \frac{n(n + 1)}{2}\lambda \iff \frac{\lambda}{2} \ge \frac{y_n}{n + 1} - \frac{y_{n - 1}}{n} = s_n - s_{n - 1}.\] Note also that we have the inequality \[s_i = \frac{y_i}{i + 1} = \frac{x_1 + 2x_2 + \cdots + ix_i}{i + 1} \le \frac{\lambda(1 + 2 + \cdots + i)}{i + 1} = \frac{i\lambda}{2},\] for all $i \in \mathbb{N}.$ In particular, upon division by $i$, it follows that $T$ is bounded above by $\lambda / 2.$ Now, suppose to the contrary that there are only finitely many $n \in \mathbb{N}$ such that $s_n - s_{n - 1} \le \lambda / 2$, and let $M \in \mathbb{N}$ be an integer such that for all $n > M$, we have $s_n - s_{n - 1} > \lambda / 2.$ We will prove the convergence of several sequences that will allow us to solve the problem. We claim that $T$ converges to $\lambda / 2.$ Suppose otherwise, and by the definition of convergence, let $\delta > 0$ be a real constant and let $M_1 \in \mathbb{N}$ be a "bounding integer" such that $t_n = \tfrac{s_n}{n} + \delta < \lambda / 2$ for all $n > M_1.$ By rearranging, it follows that $s_n < \tfrac{n\lambda}{2} - n\delta.$ Then for any integer $k > \max\{M, M_1\}$, we may write \begin{align*} s_M &< s_{M + 1} - \lambda / 2 \\ s_{M + 1} &< s_{M + 2} - \lambda / 2 \\ &\cdots \\ s_{k - 1} &< s_k - \lambda / 2 \\ s_k &< \frac{k\lambda}{2} - k\delta. \end{align*} Summation yields \[s_M < \frac{k\lambda}{2} - k\delta - \frac{(k - M)\lambda}{2} = \frac{M\lambda}{2} - k\delta.\] But note that $\tfrac{M\lambda}{2}$ is just a constant, so by taking $k$ sufficiently large so that $k\delta > \tfrac{M\lambda}{2}$, it follows that $s_M$ is negative, absurd. This is a contradiction, so $S$ converges to $\lambda / 2$, as desired. $\blacksquare$ Finally, since $X$ converges to $\lambda$, it follows that the sequence $Z = \{ix_i - (i - 1)x_{i - 1}\}_{i = 1}^{\infty}$ converges to $\lambda$ as well. However, note that $nx_n$ and $(n - 1)x_{n - 1}$ are both integers for all $n \in \mathbb{N}$, so $Z$ is a sequence of integers. But $\lambda$ is not an integer, so we cannot have a sequence of integers that converges to $\lambda$, contradiction. $\square$

stephcurry wrote: This doesn't make sense to me. What if you consider x = floor of n*lambda, and let the set be {1,2,3...x}? Its obviously true then I'm not quite sure what you're saying. It seems like what you're pointing out is noting that this problem works when $A = \mathbb{Z}^{+}$.

It's integer bounding from what I've heard: let $x_n$ be the number of times $n$ appears in $A$. Then $x_i \ge 0$ are integers and you want to show that it's impossible for \[ \frac{x_1+\dots+x_n}{n} \le \lambda < \frac{x_1+2x_2+\dots+nx_n}{1+2+\dots+n} \] to hold for all integers $n \ge M$. I haven't worked out the details myself but my spies assure me that it's just some bounding from here. The condition $\lambda < 1$ cannot be dropped, otherwise $x_1 = 0$, $x_2 = 2$, $x_3 = x_4 = \dots = 1$ works with $\lambda= 1$. Similarly, you need the fact that the $x_i$ are integers (or one can scale the previous construction).

What was the point of $A$ being a multiset if $A_n$ are just sets

Probably the CAMC made a typo when writing these problems up. I'm sure it's supposed to be a multiset.

Wait what that ruins my entire solution then Edit: oh jk I guess it doesn't

wait oops my solution was probably bad then... what I did was like, assume contrary and let $k$ be the largest number such that $S_k \le \frac{k(k+1)}{2}$ and let $b_0, b_1, \ldots$ be the next elements you add. then, proved that $b_x < k + 1 + \frac{x}{\lambda} - \sum_{i = 0}^x \epsilon_i$, where $\sum\epsilon_i$ is a diverging sequence ($\epsilon_i$ was on the order of $\frac{1}{x}$). then you can just show that the density of numbers will exceed $\lambda$. not sure if it's right though... or rigorous or valid or whatnot... darn

Yes, it works equally well for sets and multisets. (Really should have been formulated as a sequence problem, sorry about that). The best "linear" bounds are: For $\lambda$ irrational and any fixed $c>0$, the sum of elements less than or equal to $n$ is less than $\lambda \frac{n(n+1)}2-\frac n2+cn$ infinitely often. For $\lambda=\frac pq$ rational and any fixed $c>0$, the sum of elements less than or equal to $n$ is less that $\lambda \frac{n(n+1)}2-\frac{q-1}{2q}n+cn$ infinitely often.

Can anyone post the actual bounding part? Because I got that far and couldn't bound it... I tried letting \[ A_n = n\lambda-\sum_{i=1}^n{x_i}\ge0 \] \[ B_n = \sum_{i=1}^{n}{ix_i}-\frac{n(n+1)}{2}\lambda>0 \] because $A_n$ and $B_n$ increase/decrease nicely in parallel. Unfortunately I only wrote this down (same thing as the previous way of writing, just in different form) and said bounding works from here; will that get me any points?

Let $a_i$ denote the number of instances of $i$. Assume, for contradiction, that there exists $N$ such that for all $n>N$, $a_1 + \cdots + na_n > \frac{(n)(n+1)}{2}\lambda$. We also know that $a_1 + \cdots + a_n \le n \lambda$. Let \[f(n) = a_1 + \cdots + na_n - \frac{(n)(n+1)}{2}\lambda.\] Let $c=N+1$ and $r = \frac{c}{2}$. Let \begin{align*} g(k) &= \frac{1}{c+k} f(c+k) + \sum_{i=c}^{c+k-1} \left(\frac{1}{i}-\frac{1}{i+1}\right) f(i)\\ &= \frac{1}{c+k}\left(a_1 + \cdots + (c+k)a_{c+k}- \frac{(c+k)(c+k+1)}{2}\lambda\right) \\ &+ \sum_{i=c}^{c+k-1} \left(\frac{1}{i}-\frac{1}{i+1}\right)\left(a_1 + \cdots + ia_i - \frac{(i)(i+1)}{2}\lambda\right) \\&= \frac{1}{c} \cdot (a_1+2a_2+\cdots (c-1)a_{c-1}) + (a_c+\cdots a_{c+k}) - \frac{c+k+1}{2} \lambda - \frac{k}{2} \lambda \\ &\le (c+k) \lambda - \frac{c+k+1}{2} \lambda - \frac{k}{2} \lambda \\ &= \frac{c-1}{2} \lambda \end{align*} which is bounded above. We know $f(n) > 0$ by our assumption. Then $f(n)+f(n+1) \ge |f(n+1)-f(n)| = (n+1)\cdot |a_{n+1}-\lambda| \ge (n+1) \min(\lambda, 1-\lambda)$. Therefore \begin{align*} g(k) &\ge \sum_{i=c}^{c+k-1} \left(\frac{1}{i}-\frac{1}{i+1}\right) f(i) \\ &\ge \sum_{i = r}^{r+\frac{k}{2}} \frac{1}{2r(2r+1)} (f(2r)+f(2r+1)) \\ &\ge \sum_{i = r}^{r+\frac{k}{2}} \frac{1}{2r} \min(\lambda, 1-\lambda) \end{align*} which is unbounded, a contradiction.

Suppose FTSOC that for all $n\ge N$ the sum $S_n>\frac{n(n+1)}{2}\lambda$, for some set $A$. Furthermore, suppose that $A$ satisfies the size condition up until $n=N$. If $S_n$ does not fall less than or equal to the necessary bound for all $n \ge N$, then a greedy construction of $A$ ought to stay within the size constraints as well. The greedy construction of $A$ starting from $N+1$ is given by the following procedure: Step $1.$ Let $S=S_N$. Consider the number $N+1$. Include an instance of $N+1$ in the set if and only if failing to do so would result in $S$ being less than or equal to $\frac{(N+1)(N+2)}{2}\lambda$. If you must add $N+1$ to the set, increment the value of $S$ by $N+1$. (Since $\lambda < 1$ you will only need at most one instance of $N+1$ to "stay afloat") Step $i.$ Consider the number $N+i$. Repeat step $1$, but for the number $N+i$ instead of $N+1$. Note that, for $A$ to satisfy the bound for $n=N$, the set $A_N$ must contain at least $~\frac{N}{2}\lambda$ elements (the actual number isn't important, just the fact that it's finite). Thus, if for some very large $M$ we find that the greedy algorithm selects more than $(M-N)\lambda + \frac{N}{2}\lambda$ numbers, the multiset $A_M$ has more than $M\lambda$ elements, violating the conditions. Thus, we have reduced the problem to showing that constructing a set $A$ via the greedy algorithm results in arbitrarily large overflow--in other words, for arbitrarily large $M$, the size of $A_M$ can be arbitrarily more than $M\lambda$. For the sake of simplicity, it's equivalent to start the greedy algorithm from $1$. Case $1$: $\lambda$ is rational, so $\lambda = \frac{p}{q}$ in lowest terms. We show that there are infinitely many size-$q$ intervals $\{kq+1,\dots,(k+1)q\}$ (where $k$ is a nonnegative integer) such that more than $p$ elements are selected for within the interval by the greedy algorithm. We do this by first showing that for $k=0$. [Sketchy part incoming: if anyone has any idea how to rigorize the fact that greedy is somehow bad or suboptimal I would be very happy] [EDIT: The sketchy part is resolved at the bottom of this post I think] For $k=0$, we must show that the greedy algorithm selects at least $p+1$ elements from $\{1,2,\dots,q\}$. Suppose that only $p$ or fewer elements are selected. Then these first $p$ elements must have a total sum of at least $\frac{q(q+1)}{2}\lambda=\frac{p(q+1)}{2}$, so the average of these $p$ elements must be at least $\frac{q+1}{2}$. But this is definitely not true since the greedy algorithm does not select numbers that are evenly distributed about $\{1,2,\dots,q\}$; it certainly is "bottom-heavy" (overcompensating at the beginning because the numbers are so small). The point about greedy picking at least $p+1$ out of the first $q$ elements is proved in the bottom edit. Now we show that there are infinitely many $k>0$ where greedy selects at least $p+1$ elements as well. First of all, the sum $S_{kq}$ is bounded between $\frac{kq(kq+1)}{2}\lambda$ and $\frac{kq(kq+1)}{2}\lambda + kq$, and the sum $S_{(k+1)q}$ is bounded between $\frac{(k+1)q((k+1)q+1)}{2}\lambda$ and $\frac{(k+1)q((k+1)q+1)}{2}\lambda + (k+1)q$. The difference between $S_{kq}$ and $S_{(k+1)q}$ must be greater than or equal to \[\frac{(k+1)q((k+1)q+1)}{2}\lambda - \frac{kq(kq+1)}{2}\lambda = kpq + \frac{p(q+1)}{2}\] an infinite number of times; if not, our $S_{kq}$s are clearly not big enough for large enough $k$. Now we just do the same thing for each of these $k$: suppose the greedy algorithm picks $p$ numbers from $\{kq+1, kq+2, \dots, (k+1)q\}$, then their average must be at least $kq+\frac{q+1}{2}$, which is impossible since greedy is efficient enough. Therefore, since the greedy algorithm picks a lot more than $n\lambda$ elements of the first $n$, for arbitrarily large $n$ we get arbitrarily over $n\lambda$ elements selected. There's a small detail omitted about what happens when $S_{kq}$ is in fact larger than $\frac{kq(kq+1)}{2}\lambda$, but this turns out to work in our favor--it's like starting the greedy algorithm from $1$, but you have to keep $S_n$ above $\frac{n(n+1)}{2}\lambda + c$ for some small constant $c$ that's equal to the difference between $S_{kq}$ and $\frac{kq(kq+1)}{2}\lambda$. The greedy algorithm has an even harder time now because the lower bound is higher by a constant, so at least as many elements must be selected. Case $2$: $\lambda$ is irrational. In this case, $\lambda$ can be approximated arbitrarily closely by rational numbers. By approximating arbitrarily closely, we can carry out the above argument to arbitrarily large $k$ before the difference between $\lambda$ and its rational approximation cause the $S$ values to differ by anything at least $1$. So this again shows that, for arbitrarily large $n$ we have arbitrarily large "overflow" over $n\lambda$ when using greedy. Thus, because there is arbitrarily large overflow, there is no $N$ such that, for $n \ge N$, $S_n > \frac{n(n+1)}{2}\lambda$. In other words, since $\frac{n(n+1)}{2}$ will always catch up to the greedy construction of $A$ no matter how large of a head start you give $A$, we can't construct a valid $A$ such that all $A_n$ are large enough. The sketchy part of this argument as mentioned above is trying to prove that the greedy procedure will select elements in a bottom-heavy fashion. If this can be resolved then I feel that this may be correct. EDIT: I believe this approach works to prove why greedy can't choose fewer than $p+1$ (sketch below): The approach is to find the maximum possible "gap" between two consecutively-chosen integers with greedy. Suppose that the integer $n$ is chosen, Then the maximum possible value of $S_n$ is $\frac{n(n+1)}{2}\lambda + n$. Now suppose that the numbers $n+1$ to $n+k$ are not chosen; we find an upper bound on $k$. The lower threshold for $S$ increases by $((n+1) + (n+2) + \cdots + (n+k))\lambda = (kn + \frac{k(k+1)}{2})\lambda$. If the algorithm selects nothing from $n+1$ to $n+k$, then this sum must be less than $n$ (which was the amount by which $S_n$ exceeded $\frac{n(n+1)}{2}\lambda$). Some algebra gives $k < \frac{1}{\lambda} = \frac{q}{p}$. Roughly speaking, this means that if only $p$ integers are selected, the total size of the gaps must total up to at most approximately $q$; since there are only $p-1$ gaps between $p$ integers selected, and since the first integer selected is $1$, $p$ integers is not sufficient to ensure that $S$ always stays above the necessary threshold for $n=1$ to $n=q$. Of course, an gap between integers of size $\frac{q}{p}$ doesn't fully make sense. However, this can be rigorized (I think) by defining a distance function between two points $n+k$ and $n+1$ as $(kn + \frac{k(k+1)}{2})\lambda$; in other words, this distance function extends the notion of "sum all integers from integer $a$ to integer $b$, excluding $a$ but including $b$" in a continuous way which preserves the properties of integers.* Then formulate a "non-integer greedy algorithm" which initially selects $1$ and, after every chosen number $n$, selects next the real number $n+k$ (for $k$ increasing from $1$ as soon as $d(n+k, n+1)$ equals or exceeds $n$ (thus ensuring that $n+k$ needs to be added in order to keep the running sum $S$ above the given bound). This "non-integer greedy algorithm," by virtue of not being limited to selecting only integers, performs better than the greedy algorithm in the sense that the the $i$th real number it chooses is obviously always greater than the $i$th integer the normal greedy algorithm chooses. The first few numbers selected by the non-integer greedy algorithm are upper bounded by \[\{1, 1+q/p, 1 + 2q/p, ..., 1+(p-1)q/p, 1+q\}\] ; from $1$ to $q+1$, at least $p+1$ numbers are be selected. But when $q$ is not a multiple of $p$, $q/p$ is not an integer, so the non-integer greedy algorithm performs strictly better than the normal greedy algorithm. Thus, in this case, the $p+1$th number selected by the greedy algorithm is strictly less than $1+q$, and so from $1$ to $q$ there are at least $p+1$ numbers selected. In the case that $q$ is a multiple of $p$, since $p/q$ is in lowest terms $p=1$. In this case it is not difficult to show that the greedy algorithm selects at least $p+1=2$ numbers as well; the first number selected is always $1$, but clearly another number must be selected between $1$ and $q$ otherwise $S_q = 1 < \frac{(q+1)}{2} = \frac{q(q+1)}{2}\lambda$. Thus, at least $p+1$ out of the first $q$ elements are always selected regardless of $p$ and $q$, roughly because the frequency at which elements are selected is at least $1/\lambda$. FINAL NOTES: Apparently the idea the idea that the gaps are roughly bounded by $1/\lambda$ showed up in the bounding of other proofs. So maybe this is pretty equivalent to other solutions, just messier and far less concise. *Note about the distance function: This distance function is constructed so that $d(0, n) = \frac{n(n+1)}{2}\lambda$, and so that $d(a, b) = \frac{b(b+1)}{2}\lambda - \frac{(a-1)a}{2}\lambda$. For integer $a$ and $b$, this is the sum of the integers from $a$ to $b$ (hmm I might have an off by one error somewhere in there but as long as the start/end are correctly chosen the argument won't break). This was terribly written up and entirely horrible. I don't want to think about this any more. If anyone ever has any inclination to read this and finds a hole let me know so I can rip hair out of my skull in frustration.

Can someone verify if this is true? Assume the contrary, and suppose for all $n > N$ the sum $S_n > \frac{n(n+1)}{2}\lambda$ and $S_N \le \frac{N(N+1)}{2}\lambda$ ($N$ must exist since $A_0 = \emptyset$). Now, we incrementally add the next few elements $b_0, b_1, \ldots$. Obviously, $b_0 = N+1$. Lemma: $b_k < N + 1 + \frac{k}{\lambda} - \sum_{i = 1}^k \epsilon_i$ for some diverging series (in partial sums) $\epsilon_i$. We use induction. Assume that: \begin{align*} S_{b_k - 1} &\le \frac{(N+\frac{k-1}{\lambda} - \sum_{i = 1}^{k-1} \epsilon_i)(N+1+\frac{k-1}{\lambda} - \sum_{i = 1}^{k-1} \epsilon_i)}{2}\lambda \\ S_{(N+1)-1)} = S_N &\le \frac{(N+\frac{0}{\lambda} - \sum_{i = 1}^{0} \epsilon_i)(N+1+\frac{0}{\lambda} - \sum_{i = 1}^{0} \epsilon_i)}{2}\lambda \\ &= \frac{N(N+1)}{2}\lambda \end{align*} So it is satisfied for the base case $k = 1$. Then, we have: \begin{align*} S_{b_{k+1} - 1} &\le \frac{(N+\frac{k}{\lambda} - \sum_{i = 1}^k \epsilon_i)(N+1+\frac{k}{\lambda} - \sum_{i = 1}^k \epsilon_i)}{2}\lambda + b_k \\ &< \frac{(N+\frac{k}{\lambda} - \sum_{i = 1}^k \epsilon_i)(N+1+\frac{k}{\lambda} - \sum_{i = 1}^k \epsilon_i)}{2}\lambda + (N+1+\frac{k}{\lambda} - \sum_{i = 1}^k \epsilon_i) \\ &= \frac{(N+\frac{k+2}{\lambda} - \sum_{i = 1}^k \epsilon_i)(N+1+\frac{k}{\lambda} - \sum_{i = 1}^k \epsilon_i)}{2}\lambda \\ &= \frac{(N+\frac{k+1}{\lambda} - \sum_{i = 1}^k \epsilon_i)(N+1+\frac{k+1}{\lambda} - \sum_{i = 1}^k \epsilon_i) - \frac{1}{\lambda}\big(\frac{1}{\lambda}-1\big)}{2}\lambda \\ &\le \frac{(N+\frac{k+1}{\lambda} - \sum_{i = 1}^k \epsilon_i - \delta)(N+1+\frac{k+1}{\lambda} - \sum_{i = 1}^k \epsilon_i - \delta)}{2}\lambda \end{align*} So: \begin{align*} \delta(2N + 1 + 2\frac{k+1}{\lambda} - 2\sum_{i = 1}^k \epsilon_i) + \delta^2 &\le \frac{1}{\lambda}\big(\frac{1}{\lambda}-1\big) \\ \delta &< \frac{\frac{1}{\lambda}\big(\frac{1}{\lambda}-1\big)}{2N + 1 + 2\frac{k+1}{\lambda} - 2\sum_{i = 1}^k \epsilon_i)} - \phi \\ \delta &< \frac{\frac{1}{\lambda}\big(\frac{1}{\lambda}-1\big) - \phi + \psi}{2\frac{k}{\lambda}} \\ \delta &< \frac{(1 - \lambda) - \lambda\phi - \lambda\psi}{2k\lambda} \end{align*} Where $\lambda\phi << (1 - \lambda)$ since the $\delta^2$ term is small compared to the others, so $\phi$ is very small. Then, let $\epsilon_{k+1} = \sup{\delta}$, so $\epsilon_{k+1} = \frac{(1 - \lambda) - \lambda\phi - \lambda\psi}{2k\lambda}$. Now, when $k$ is large, $\psi$ is very small, as the $\frac{k+1}{\lambda}$ term is much larger than the others, so for large $k$, we have $\epsilon_k = \frac{c'}{k} - \delta \ge \frac{c}{k}$ for some constant $c < c'$ and small $\delta$. Then, summing, we have $\sum_{k = 1}^{\infty} \epsilon_k = c\sum_{k = 1}^{\infty} \frac{1}{k} = \infty$, and is thus divergent. Finishing the induction: \begin{align*} S_{b_{k+1} - 1} < \frac{(N+\frac{k+1}{\lambda} - \sum_{i = 1}^{k+1} \epsilon_i)(N+1+\frac{k+1}{\lambda} - \sum_{i = 1}^{k+1} \epsilon_i)}{2}\lambda \\ b_{k+1}-1 < N+\frac{k+1}{\lambda} - \sum_{i = 1}^{k+1} \epsilon_i \\ b_{k+1} < N + 1 + \frac{k+1}{\lambda} - \sum_{i = 1}^{k+1} \epsilon_i \end{align*} Which follows from the condition that $S_{b_{k+1} - 1} > \frac{(b_{k+1}-1)(b_{k+1})}{2}\lambda$, as desired. Let the number of elements in $A_N$ be $x$. Now, for some $b_k$, the total number of elements in $A_{b_k}$ is: \begin{align*} x + k + 1 &\le (N + 1 + \frac{k+1}{\lambda} - \sum_{i = 1}^{k+1} \epsilon_i)\lambda \\ x + k + 1 &\le N\lambda + \lambda + k + 1 - \lambda\sum_{i = 1}^{k+1} \epsilon_i \\ \sum_{i = 1}^{k+1} \epsilon_i &\le N - \frac{x}{\lambda} \end{align*} But, $\sum_{i = 1}^{k+1} \epsilon_i$ is not bounded, but $N - \frac{x}{\lambda}$ is constant, a contradiction. Thus, there must exist infinitely many $n$ such that $S_n \le \frac{n(n+1)}{2}\lambda$. The kinda sketchy part is the treatment of $\epsilon_{k+1}$, as there is the pesky $\delta^2$ there. I'm pretty sure that $\phi$ and $\psi$ are both very very small and can be essentially ignored, but I'm not sure if my lack of rigor in treating them would cause my solution to be graded 0+ or 7-. Does anyone have any ideas?

I prove the problem for any non-integer positive $\lambda$. Rename $a=\lambda$ because I'm lazy. So let $x_n = na - (a_1+...+a_n) \ge 0$ where $a_k$ is the number of instances of $k$, and notice $\{x_n\} = \{na\}$. For $n>N$, notice that $(1+...+n)a < 1a_1+...+na_n = n(a_1+...+a_n)-((a_1)+(a_1+a_2)+...+(a_1+...+a_{n-1})) = n(na - x_n)-((1a-x_1)+...+((n-1)a-x_{n-1}) \Rightarrow nx_n < x_1+...+x_{n-1}$. Let $S_n=(x_1+...+x_n)/n$ and notice $S$ is decreasing for $n>N$. Since $S_n>0$ always, we have that there exists a number $0<\nu = \displaystyle\lim_{n \rightarrow \infty} S_n$, and $\nu < S_n$ for all $n>N$. Now, if $a$ is irrational, then look at the interval $\mathcal{I}=(\{ nu\}+\epsilon_1, \{ nu\} + \epsilon_2)$ where $\{nu\}+\epsilon_1 < \{ nu \}+\epsilon_2 < 1$. By Kronecker's Theorem, there are infinitely many $n$, with a "constant frequency", that satisfy $\{ na \} \in \mathcal{I}$. Now choose an $M>N$ such that $S_n < \nu + \epsilon_1$ for all $n>M$. Then, for any $n>M$ that satisfies $\{ na \} \in \mathcal{I}$, we know $x_n < S_{n-1}$ and $\{ x_n \} > \{nu\}+\epsilon_1$, and therefore there's a positive constant $C$ such that there exist $n$'s with a constant frequency $F:=|\mathcal{I}|$ (and $n>M$) such that $x_n < \nu - C$, clearly impossible since then the limit is at most $\nu - CF$ (because even the $n$'s that don't satisfy $x_n < \nu -C$ still are arbitrarily close to $\nu$.) If $a$ is rational, then notice $x_n$ takes on a finite amount of possible values for $x_n$ and thus with a linear frequency (since $a$ is not integer), it takes a value $< \nu - C$ for some positive constant $C$, so done.

So my solution was kind of weird, but I really want to know if I majorly screwed up or something, since I fully didn't expect to get close on a #6.

Again, I would not be surprised if there's a huge mistake in this solution, but I thought I'd throw it into the mix for feedback.

I feel really sorry for the graders of this problem... half the solutions are incomprehensible, and the other half are, well, trivially less incomprehensible.

I don't even think that's true lol.

Since people are very confused about this problem, let me give the official solution - which is the same as JuanOrtiz's. I found the solution quite clear, probably because I thought about it the "right" way. Let $a_n$ be the size of (the multiset) $A_n$ and set $b_n=n\lambda-a_n\geq 0$. Note then that the sum of elements in $A_n$ is $$a_1+2(a_2-a_1)+\ldots+n(a_n-a_{n-1})=na_n-a_{n-1}-\ldots-a_1=$$$$=n(n\lambda-b_n)-((n-1)\lambda-b_{n-1})-\ldots-(\lambda-a_1)=\lambda \frac{n(n+1)}2-nb_n+b_{n-1}+\ldots+b_1$$ and hence if it is eventually $\geq \lambda \frac{n(n+1)}2$ we conclude that $$(\star) \phantom{iura} b_n\leq \frac{b_1+\ldots+b_{n-1}}{n}, \forall n\geq n_1$$ In particular, the next term is less than the average of the preceding ones. It is then somewhat logical to guess that such a sequence should eventually decrease below zero, which would be a contradiction, UNLESS it becomes "almost constant" i.e. converges. This would mean that consecutive terms would get arbitrarily close to each other. But $|b_n-b_{n-1}|=|a_n-a_{n-1}-\lambda|$ is bounded below away from zero since $\lambda$ is not an integer, contradiction! Below is the technical realization of this idea: Let $M=\max(b_1, \ldots, b_{n_1-1})$ and therefore it is immediate that $b_n\leq M$ for all $n$, using the above inequality. Moreover, set $\delta=\min(\lambda, 1-\lambda)$ and $\epsilon=\delta/3$. Note that $|b_n-b_{n-1}|=|a_n-a_{n-1}-\lambda|\geq \delta$ and from here we immediately deduce that $b_n+b_{n-1}\leq 2M-\delta<2(M-\epsilon)$. Hence the average of any two consecutive terms is $\leq M-\delta/2<M-\epsilon$ and invoking $(\star)$ we conclude that in fact $$a_n<M-\epsilon, \forall n\geq n_1$$ Repeating the same argument, we conclude that the average of any two consecutive terms is $\leq M-\epsilon-\delta/2$ beyond $n_1$. Since $\delta/2>\epsilon/3$, taking $n$ much bigger than $n_1$ would ensure that $\frac{b_1+\ldots+b_{n-1}}{n}<M-\epsilon-\epsilon$ that is $$b_n<M-2\epsilon, \forall n\geq n_2$$ where $n_2$ is large enough. The rest is now clear: iterating the above argument we obtain by induction a sequence $n_k$ such that $$b_n<M-k\epsilon, \forall n\geq n_k$$ and this is a contradiction for $k>M/\epsilon$. The stronger assertion I mentioned in my previous can be done in the same way, however instead of taking the average of two consecutive terms we take the average of $m$ consecutive terms where $m$ is large enough. We invoke the (simple case of) Weyl's equidistribution theorem for $\lambda$ irrational, which states that the fractional parts of $n\lambda$ are equidistributed in $[0,1]$ (so their "average" is $1/2$), or for rational $\lambda$, the fact that the average of the fractional parts of $n\lambda$ is $(q-1)/{2q}$. Using this we can show that for large $m$ the average of $m$ consecutive terms is $\displaystyle < M-\left(\frac 12+c\right)$ respectively $\displaystyle < M-\left (\frac{q-1}{2q}+c\right)$ and the solution can be adapted from there. Finally the sequence $\displaystyle \left\lceil\frac n{\lambda}\right\rceil$ produces an example that shows the above are best possible. I'm curious if one can replace "any $c>0$" with a sub-linear estimate.

iura wrote: Since people are very confused about this problem, let me give the official solution - which is the same as JuanOrtiz's. I found the solution quite clear, probably because I thought about it the "right" way. Let $a_n$ be the size of (the multiset) $A_n$ and set $b_n=n\lambda-a_n\geq 0$. Note then that the sum of elements in $A_n$ is $$a_1+2(a_2-a_1)+\ldots+n(a_n-a_{n-1})=na_n-a_{n-1}-\ldots-a_1=$$$$=n(n\lambda-b_n)-((n-1)\lambda-b_{n-1})-\ldots-(\lambda-a_1)=\lambda \frac{n(n+1)}2-nb_n+b_{n-1}+\ldots+b_1$$ and hence if it is eventually $\geq \lambda \frac{n(n+1)}2$ we conclude that $$(\star) \phantom{iura} b_n\leq \frac{b_1+\ldots+b_{n-1}}{n}, \forall n\geq n_1$$ Ah, the $b_i$ are a much nicer way of doing the computation (better than the convoluted $x_i$ sequence I had above) -- once you get to ($\star$) above it's very clear what to do next. Thanks.

Let $a_k$ be the number of times $k$ appears in $A$, and let $b_n=a_1+2a_2+3a_3+...+na_n$. Assume for some $r$, if $n>r$ then $b_n=\frac{n(n+1)}{2}\lambda+\epsilon_n$, where $\epsilon_n > 0$. Since $a_n=\frac{b_n-b_{n-1}}{n}$, $n\lambda \geq a_1+a_2+...+a_r+a_{r+1}+...a_n = a_1+a_2+...+a_r+\frac{b_{r+1}-b_r}{r+1}+\frac{b_{r+2}-b_{r+1}}{r+2}+...+\frac{b_{n-1}-b_{n-2}}{n-1}+\frac{b_{n}-b_{n-1}}{n}$ $=a_1+a_2+...+a_r-\frac{b_r}{r+1}+\frac{b_{r+1}}{(r+1)(r+2)}+\frac{b_{r+2}}{(r+2)(r+3)}+...+\frac{b_{n-1}}{(n-1)n}+\frac{b_n}{n}$ $>a_1+a_2+...+a_r-\frac{b_r}{r+1}+\frac{(n-r-1)\lambda}{2}+\frac{(n+1)\lambda}{2}+\frac{\epsilon_{r+1}}{(r+1)(r+2)}+\frac{\epsilon_{r+2}}{(r+2)(r+3)}+...+\frac{\epsilon_{n-1}}{(n-1)n}$. So it is only necessary to show that $\sum{\frac{\epsilon_k}{k(k+1)}}$ diverges to obtain the desired contradiction (by assumption there are only a finite number of negative terms). Note that if $a_{t+1}=0$, then $b_t >\frac{(t+1)(t+2)\lambda}{2}$, so $\epsilon_t >(t+1)\lambda$. Thus if $z_1<z_2<z_3...$ are the numbers such that $a_{z_i}$ are the zero elements of $A$, then it is only necessary to show that $\sum\frac{\lambda}{z_k-1}$ diverges. Assume that for some $k$, $z_k > \frac{2k}{1-\lambda}$. Then choose $l$ such that $\frac{2k}{1-\lambda}>l>\frac{k}{1-\lambda}$. Among the numbers $a_1,a_2,...,a_l$, there are at most $k$ zeros, so $a_1+a_2+...+a_l > l-k>l-l(1-\lambda)=l\lambda$, a contradiction. So $z_k < \frac{2k}{1-\lambda}$, which means that $\sum\frac{\lambda}{z_k-1}$ is harmonic (or larger) and so diverges.

Suppose the problem is false. Let $b_n$ denote the number of times that $n$ appears in $A$. We have then that \[b_1+b_2+\cdots+b_n\le n\lambda\text{ }\forall n\in\mathbb{N},\]and that there exists some $N$ such that \[b_1+2b_2+\cdots+nb_n>\frac{n(n+1)}{2}\lambda\]for all $n\ge N$. Let $y_i=b_i-\lambda$. We have then that \[y_1+\cdots+y_n\le 0\]for all $n$, and \[y_1+2y_2+\cdots+ny_n>0\]for all $n\ge N$. Let $s_n=y_1+\cdots+y_n$. We have that \[1y_1+\cdots+ny_n = n(y_1+\cdots+y_n)-(y_1)-(y_1+y_2)-\cdots-(y_1+\cdots+y_{n-1})=ns_n - (s_1+s_2+\cdots+s_{n-1}).\]Thus, we have \[s_n>\frac{s_1+\cdots+s_{n-1}}{n}=:p_n\]for all $n\ge N$, and $s_n\le 0$ for all $n$. Note that $s_n>p_N$ for $n>N$. Now note that $|s_n-s_{n-1}|=|y_n|>\delta$ for some positive constant $\delta$. Thus, for large enough $n$, either $s_n$ or $s_{n-1}$ is at least $p_N+\delta$, so for large enough $n$, the $p_n$ drops asymptotically by $\delta/2$. Concretely, we have $p_n>p_N+\delta/1000$ for large enough $n$. Repeating this argument, we see that $p_n$ grows without bound, so eventually $p_n>0$, which can't be since all the $s_n\le 0$. Thus, we have the desired contradiction. $\blacksquare$

Suppose there exists some $n_0$ such that for all $n \ge n_0$, the sum of the elements of $A_n$ is greater than $\frac{n(n+1)}{2}\lambda$. For each $n$, we define \[x_n = n\lambda - |A_n| \ge 0.\]For $n \ge n_0$, we have that \[\sum_{i=1}^n |A_i| + \sum_{i=1}^n x_i = \sum_{i=1}^n i\lambda = \frac{n(n+1)}{2}\lambda < \sum_{a \in A_n}a = \sum_{i=1}^n i(|A_i| - |A_{i-1}|) = n|A_n| - |A_{n-1}| - \dots - |A_1|.\]Rearranging, we see that \[n(n-1)\lambda - \sum_{i=1}^{n-1} x_i = 2\sum_{i=1}^{n-1}i\lambda - \sum_{i=1}^{n-1} x_i = 2\sum_{i=1}^{n-1} |A_i| + \sum_{i=1}^{n-1} x_i < (n-1)|A_n| - x_n = n|A_n| - n\lambda = n(n-1)\lambda-nx_n.\]Dividing by $n$ and rearranging once more gives \[x_n < \frac{x_1+\dots + x_{n-1}}{n}.\]We then observe that the sum \[\frac{x_1+\dots + x_{n-1}}{n}\]must strictly decrease as $n$ increases. Now, we observe that $|x_{n+1}-x_n| = |(n+1)\lambda - |A_{n+1}| - n\lambda + |A_n|| = |\lambda - |A_{n+1}|+|A_n||>\epsilon$ for all $n$ and some $\epsilon > 0$ because the $|A_i|$ are integers and $\lambda$ is not. Since the upper bound is strictly decreasing, at some point we must have that $x_n < M$ for some $M$ and $N_0$ with $n > N_0$. We note that for all such $n$, we have $x_n+x_{n+1} < 2M-\epsilon$. Then, the sum \[\frac{x_1+\dots + x_{n-1}}{n}\]must approach being upper-bounded by $M-\epsilon/2$. In particular, we eventually have $x_n < M-\epsilon/3$ for all $n > N_1$. Iterating will eventually give an upper bound less than or equal to $0$, absurd because each $x_i$ is at least $0$. Thus, we have a contradiction.

Remark: Insane morale booster. Suppose the number $n$ appears in $A$ a total of $a_n$ times. By the problem, we have\[a_1 + \ldots a_k \leq k\lambda\]for all positive integers $k$. FTSoC the problem statement is false. Then, there must exist constant $C$ such that for all $m \geq C$,\[\sum_{g \in A_m} g = a_1 + 2a_2 + \ldots + ma_m > \frac{m(m+1)}{2}\lambda.\]Define the new sequence of reals $b_i = a_i - \lambda$. Nicely, our previous two equations in terms of $b_i$ become:\[b_1 + b_2 + \ldots + b_k \leq 0 \text{ for all } k \in \mathbb{Z}_+ \text{ and } b_1 + 2b_2 + \ldots + mb_m > 0 \text{ for all } m \geq C.\]Yet again define a new sequence $c_i = b_1 + \ldots b_i$. It follows that for all $i$, we have $c_i \leq 0$ and\[b_1 + 2b_2 + \ldots + mb_m = mc_m - (c_1 + \ldots + c_{m-1}) > 0\]for all $m \geq C$. Hence $c_m > \tfrac{c_1 + \ldots + c_{m-1}}{m}$ for each sufficiently large $m$. Now for the last time, define the new sequence $d_i = \tfrac{c_1 + \ldots c_{i-1}}{i}$ for all $i$ where all $c_j$ terms are defined. Proving that the sequence $d_i$ is unbounded above will provide our desired contradiction since all $c_i$ are $\leq 0$. $c_m > d_m$ for $m \geq C$. Note that for all $i$, we have $|c_{i+1} - c_i| = |b_{i+1}| = |a_{i+1} - \lambda| \geq \text{min}(\lambda, 1 - \lambda) = \epsilon$, a constant. Furthermore, check that for sufficiently large $m > C$, that $c_m > d_m > d_C$. Hence, one of $c_m, c_{m-1}$ is $\geq d_C + \epsilon$ for all large enough $m$, and arguing further yields that $d_m$ grows by $c\epsilon$ for some positive constant $c$ after certainly many moves. Repeat until $d_{\text{something}} > 0$, a contradiction, as desired. $\blacksquare$

Suppose for each $i$, there are $a_i$ occurrences of $i$ in $A$. Assume that the problem is false, then for some $N$, we have \begin{align*} a_1+\cdots+a_n &\le n\lambda \qquad \qquad \forall n. \\ 1a_1+\cdots+na_n &> \tfrac{n(n+1)}{2}\lambda \qquad \forall n\ge N. \end{align*}Let $b_i=a_i-\lambda$. Then $b_1+\cdots+b_n\le 0$ for all $n$, and $1b_1+\cdots+nb_n>0$ for all $n\ge N$. Let $d_k:=-(b_1+\cdots+b_k) = k\lambda - (a_1+\cdots+a_k)$. Then $d_n\ge 0$ for all $n$, and the second condition above becomes \[ d_n < \frac{d_1+\cdots+d_{n-1}}{n}=:s_n \qquad \forall n\ge N \]after manipulation. Claim: $(s_n)$ and $(d_n)$ are bounded above. Proof: We claim $(s_n)$ is eventually strictly decreasing, which finishes since $0\le d_n < s_n$. Indeed, \begin{align*} s_n > s_{n+1} &\iff \frac{d_1+\cdots+d_{n-1}}{n}>\frac{d_1+\cdots+d_n}{n+1} \\ &\iff (n+1)(d_1+\cdots+d_{n-1}) > n(d_1+\cdots+d_n) \\ &\iff d_1+\cdots+d_{n-1} > nd_n \\ &\iff s_n>d_n, \end{align*}which is true for all sufficiently large $n$. $\blacksquare$ We haven't yet used the integer property, which gives us another condition: for all $k$, \[ |d_k-d_{k-1}| = |b_k| \ge \min(\lambda, 1-\lambda)=\varepsilon, \qquad (\heartsuit) \]a positive constant. The idea is to now use the fact that $s_n$ is almost an average of the previous $d_i$'s to get a contradiction. From $(\heartsuit)$, it is possible that the $(d_i)$'s essentially oscillate between two values separated by $\varepsilon$, but this is bad since then $s_n$ will eventually be trapped between these two values, and then we will not have $d_n<s_n$ for all $n$. This suggests using a ``global'' argument. Suppose $(s_n)$ and $(d_n)$ are bounded above by $S$ for all $n$. Consider the interval $I:=[S-\varepsilon, S)$. Over all $n\ge N$, we claim at most $\tfrac12$ of $n$ lie in $I$. Indeed, by $(\heartsuit)$, if $d_n\in I$, then $d_{n+1}$ cannot go up by $\varepsilon$, so it must go down, i.e. $d_{n+1}\le d_n-\varepsilon \not \in I$, proving the claim. Therefore, \[ s_n = \frac{d_1+\cdots+d_{n-1}}{n} < \frac{d_1+\cdots+d_{n-1}}{n-1} \le S-\frac12 \varepsilon. \]Since $d_n<s_n$ for all $n\ge N$, hence \[ d_n < s_n < S-\tfrac12 \varepsilon \qquad \forall n\ge N. \]Now we can replace $S$ by $S-\tfrac12 \varepsilon$ and repeat the same argument ($N$ will have to grow larger, but that's fine). Eventually we will get $d_n$ is bounded above by a negative number, contradiction, since $d_n\ge 0$.

Let $a_i$ be the number of occurences of $i$ in $A$. We know $\sum\limits_{i=1}^n a_i \le n\lambda$. We wish to show for any $C$, there exists $n>C$ such that $\sum\limits_{i=1}^n ia_i \le \frac{n(n+1)}{2}\lambda$. Let $T_i= n\lambda - \sum\limits_{j=1}^i a_i$. Then this inequality becomes $T_i\ge 0$ and $T_i< \frac 1n \sum\limits_{i=1}^{n-1} T_i$ for $n>C$. Setting $T_i=\frac{T_1}{2}-\epsilon$ seems to suffice, but we have another condition: $T_m\equiv m\lambda(\bmod\; 1)$!! First of all, this condition suggests $U_n=\frac {1}{n+1} \sum\limits_{i=1}^{n} T_i$ is actually decreasing. If I show it decreases by a nontrivial amount, I'm done, since it decreases by a nontrivial amount however many times I want until I get $U_n<0$. Note $|T_m-T_{m-1}| \ge \min\{\lambda,1-\lambda\}=D$. If $U_n<M$ for all $n>\max\{K,C\}$ for some constant $K$, then we note $T_m+T_{m-1} \ge 2\max\{T_m,T_{m-1}\} - |T_m-T_{m-1}| \ge 2M-D$, so we can show that $U_n<M-\frac{D}{3}$ for all $n$ large.

Let $\lambda = \frac{1}{k}$ for some real $k > 1$. I will prove by contradiction, so assume there exists some $c$ such that $S_n > \frac{n(n+1)}{2k}$ for all $n \ge c$, where $S_n$ is the sum of the elements in $A_n$. Note that if this is not true, then you will be able to find infinite numbers as there is no upper bound. Assume $n \ge c+1$. Let $c_n$ be the smallest positive integer such that $\frac{c_n(c_n+1)}{2k} \ge S_n > \frac{n(n+1)}{2k}$ for all $n$. Therefore in order for $S_{c_n} > \frac{c_n(c_n+1)}{2k}$, we must have $S_{c_n} = S_n + p$ for some positive integer $p$. We wish to maximize this value of $p$, yet also have $|A_{c_n}| = 1+|A_n|$. For example, we don't need $A_{c_n}$ to have two values of $c_n$, even though it satisfies the properties because we can switch this $c_n$ with a bigger number such that it affects the sums of the later sets because it is redundant for smaller $n$. Therefore, we let $p = c_n$ such that it is optimal. Now, notice that if we let $d = \frac{k}{2(c_n+k)}$, $$\frac{(c_n+k-d)(c_n+k+1-d)}{2k} > \frac{c_{n}^2+2kc_n+k^2 + (1-2d)(c_n+k)}{2k} = \frac{c_n(c_n+1)}{2k}+c_n+\frac{k^2-2d(c_n+k)}{2k}$$$$> S_n+c_n+\frac{k-k}{2k} = S_{c_n}.$$ If we let $d_n$ be the positive real such that $\frac{d_n(d_n+1)}{2k} = S_n$, we see that $\lfloor d_n \rfloor = c_n$, and $d_n+(k-\frac{k}{2(c_n+k)}) = d_{n+1}$. Lemma: Let $e_n = c_{n+1}-c_n$. I claim that there exists infinite $e_i$ where $e_i = k-1$. Proof: We just have to prove that $Q = \frac{k}{2(c_n+k)}+\frac{k}{2(c_{n+1}+k)}+\frac{k}{2(c_{n+2}+k)}+\ldots$ is unbounded. We assume for the sake of contradiction that $e_n = k$ for all $n$ (note that $\frac{k}{2(c_n+k)}$ is much smaller than $k$ for large $n$. We have $$Q = k(\frac{1}{2(c_n+k)}+\frac{1}{2(c_n+2k)}+\frac{1}{2(c_n+3k)}+\ldots).$$This is true as the denominators form an arithmetic sequence, so we can always group consecutive fractions such that they sum to a number greater than some constant, and therefore the sum is infinite. With this lemma, we see that there contains a sub-multiset of $A$ whose range is $mk$ but contains $m+p$ elements for any value of $p$ and for some positive integer $m$. These sub-multisets are the multisets that contain consecutive elements of $A$ that are greater than or equal to $n$. Therefore, $p$ is unbounded and we will eventually have $|A_n| > \frac{n}{k}$, which is a contradiciton. $\blacksquare$ Remarks: My solution is almost completely different from others so I'm hesitant to even put this on. Mine relies on the "optimal strategy" which is never a good idea in oly except in combo, and I read through other's solutions and theirs are basically completely algebra. However, I'm pretty sure this is correct.

What a crunchy problem For any positive integer $k$, let $a_k$ be the number of times $k$ appears in $A$, let \[r_k=a_1+a_2+\cdots+a_k-k\lambda,\]and let \[R_k=a_1+2a_2+\cdots+ka_k-\frac{k(k+1)}{2}\lambda.\]Note that $r_k$ is positive for any $k$, and assume FTSOC that $R_k$ is positive for sufficiently large $k$. Observe that \[r_n=\frac{r_1+r_2+\cdots+r_{n-1}-R_n}{n}<\frac{r_1+r_2+\cdots+r_{n-1}}{n-1}\]for sufficiently large $n$, so $\frac{r_1+r_2+\cdots+r_n}{n}$ is decreasing. Notice that the fractional part of $r_n$ is equal to the fractional part of $-n\lambda$. Now, we prove by casework that $r_n$ is negative for large enough $n$, which gives a contradiction. Case 1: $\lambda \leq \frac{1}{2}$. The proof has a bunch of details. Left as an exercise to the reader. Case 2: $\lambda>\frac{1}{2}$. Similar to Case 1. Remark: The motivation is to assign variables to nice expressions like $r_k$ and $R_k$ then do some magic and hope that things work out.

Suppose $s_n = |A_n|$ so we have $s_n \le n \lambda$. The sum of elements in $A_n = n(s_n - s_{n-1}) + (n-1)(s_{n-1}-s_{n-2}) + \cdots + 2(s_2 - s_1) + s_1 = ns_n - \frac{s_1 + s_2 + \cdots + s_{n-1}}{n}$ which we ftsoc may assume is $> \frac{n(n+1)\lambda}{2}$ for big $n$, let $a_n = \frac{s_1 + s_2 + \cdots + s_{n-1}}{n}$ so we have $s_n - a_n > \frac{(n+1) \lambda}{2}$. Let $c_n = n \lambda - s_n$ and let $d_n = \frac{c_1 + c_2 + \cdots + c_{n-1}}{n}$ so this rearranges to just $d_n > c_n$ for all big $n$. Note that $d_n$ is strictly decreasing eventually because $c_n < d_n$ eventually. Now, to use the fact that we were given integers, note that $c_{i+1} - c_i = \lambda - $ some integer things, so we have at least that $|c_{i+1} - c_i| > C$ for some constant $C$ always. Let $M$ be a number greater than all the $d_i$'s. The point is that since $c_i$'s keep oscillating by at least some value, eventually, the $d_i$'s will become smaller, on average and so since $c_n < d_n$, the $c_n$'s too, and we just iterate this. Indeed, observe that eventually, we will have $d_i < M - \frac{C}{2} + O \left(\frac{1}{i} \right)$. Take $i$ big enough, replace $M$ with $M - \frac{C}{2}$ and repeat so eventually we get that some $d_i$ is negative, impossible, so we are done. $\blacksquare$

Does this work? I have horribly fakesolved this problem in the past so I am worried I did it again Let $a_i$ denote the number of times $i$ appears in $A$. The condition is then equivalent to $a_1+\cdots+a_n\leq n\lambda$, and we wish to prove that there are infinitely many $n$ with $b_n:=a_1+2a_2+\cdots+na_n \leq \tfrac{n(n+1)}{2}\lambda$. Suppose this second fact is not true, i.e. there exists some positive integer $N$ such that for $m>N$, we have $b_m>\tfrac{m(m+1)}{2}\lambda$. Pick $n$ to be a massive integer and consider the sum $$\frac{b_n}{n}+\frac{b_{n-1}}{n(n-1)}+\frac{b_{n-2}}{(n-1)(n-2)}+\cdots+\frac{b_{N+1}}{(N+1)(N+2)}=a_n+a_{n-1}+\cdots+a_{N+1}+(\text{sum of smaller terms with coefficients $<1$})<a_n+\cdots+a_1\leq n\lambda.$$On the other hand, by using $b_M>\tfrac{m(m+1)}{2}\lambda$, we find that the LHS sum is at more than $$\frac{n+1}{2}\lambda+(n-N-1)\frac{\lambda}{2}=\left(n-\frac{N}{2}\right)\lambda.$$The idea is now to apply some stronger estimate to some of the $b_i$ that increases the lower bound for the LHS by some unbounded function (in this case, log), which then implies a contradiction if $n$ is large enough, since $\tfrac{N}{2}\lambda$ is a constant. Observe that if $a_k=0$, then we must actually have $b_{k-1}=b_k \implies b_{k-1} \geq \tfrac{k(k+1)}{2}\lambda$. If we apply this sharper estimate to some term in the LHS, we find that our lower bound increases by $$\frac{\frac{k(k+1)}{2}\lambda}{k(k-1)}-\frac{\frac{k(k-1)}{2}\lambda}{k(k-1)}=\frac{k\lambda}{k(k-1)}=\frac{\lambda}{k-1}.$$On the other hand, for any $m>N$, we must have at least $(1-\lambda)m-N$ zeroes in the multiset $\{a_{N+1},\ldots,a_m\}$, since otherwise it contains more than $m\lambda$ nonzero terms, hence $a_1+\cdots+a_m>m\lambda$. Let $t=\lfloor\sqrt{n}\rfloor$ and consider $m=t,2t,\ldots,t^2$; by taking $n$ large enough, we can make $t \gg N$, so $(1-\lambda)t \gg N$ as well (I'm not sure if this is super necessary, but it makes things cleaner). Define the sequence $c_1,c_2,\ldots,c_t$ such that there are precisely $c_i$ zeroes among $a_{(i-1)t+1},\ldots,a_{it}$, except when $i=1$ in which case we look at $a_{N+1},\ldots,a_t$. Then we should have $c_1+\cdots+c_i \geq (1-\lambda)it-N$, and we can increase our lower bound for the LHS by $$\sum_{i=1}^t \frac{c_i\lambda}{it-1}.$$By smoothing, this is minimized when equality holds everywhere in the inequalities for $c_i$, in which case $c_1=(1-\lambda)t-N$ and $c_2=\ldots=c_t=(1-\lambda)t$, so by dropping the first term this sum is at least $$\sum_{i=2}^t \frac{t\lambda(1-\lambda)}{it-1}>\sum_{i=2}^t \frac{t\lambda(1-\lambda)}{it}=\lambda(1-\lambda)\sum_{i=2}^t \frac{1}{i}.$$But for $n$ large enough, so that $t$ is large enough, the lower bound for the LHS will increase by more than $\tfrac{N}{2}\lambda$, since the harmonic series diverges. Therefore for sufficiently large $n$ we find that $a_n+\cdots+a_1>n\lambda$: contradiction. $\blacksquare$

CyclicISLscelesTrapezoid wrote: What a crunchy problem For any positive integer $k$, let $a_k$ be the number of times $k$ appears in $A$, let \[r_k=a_1+a_2+\cdots+a_k-k\lambda,\]and let \[R_k=a_1+2a_2+\cdots+ka_k-\frac{k(k+1)}{2}\lambda.\]Note that $r_k$ is positive for any $k$, and assume FTSOC that $R_k$ is positive for sufficiently large $k$. Observe that \[r_n=\frac{r_1+r_2+\cdots+r_{n-1}-R_n}{n}<\frac{r_1+r_2+\cdots+r_{n-1}}{n-1}\]for sufficiently large $n$, so $\frac{r_1+r_2+\cdots+r_n}{n}$ is decreasing. Notice that the fractional part of $r_n$ is equal to the fractional part of $-n\lambda$. Now, we prove by casework that $r_n$ is negative for large enough $n$, which gives a contradiction. Isn't $r_k$ always negative by definition?

Let $a_i$ denote the number of elements of $A_i$ of value $i$. Then, it follows that \[ s_n = a_1 + a_2 + \dots + a_n \le n\lambda \]FTSOC assume that for sufficiently large $n$, that \[ S_n = a_1 + 2a_2 + \dots + na_n > \frac{n(n+1)}{2} \lambda. \]Define $t_n = n\lambda - s_n$ and $T_n = S_n - \frac{n(n+1)}{2}\lambda$ which are both nonnegtaive. Claim: For sufficiently large $n$, $\frac{1}{n} \sum_{i=1}^{n-1} t_n > t_{n+1}$ is decreasing and thus converges to some value $C$. Proof. Note that $\sum_{i=1}^n s_i + S_n = (n+1)s_n$ or in another words $\sum_{i=1}^n t_i - T_n = (n+1)t_n$. This simplifies as \[ \frac1n \sum_{i=1}^{n-1} t_i \ge t_n \]Then, it follows that \[ \frac{1}{n+1} \sum_{i=1}^{n} t_i \le \frac{1}{n+1} \sum_{i=1}^{n-1} t_i + \frac{1}{n+1} \cdot \frac{1}{n} \sum_{i=1}^{n-1} t_i \le \frac1n \sum_{i=1}^{n-1} t_i. \]$\blacksquare$ However, $t_{n+1} - t_n = ((n+1)\lambda - s_{n+1}) - (n\lambda - s_n) = \lambda - (s_n - s_{n+1})$ so $|t_{n+1} - t_n| > \min\{\lambda, 1 - \lambda\}$. Since all sufficiently large $t_n$ lie in $[0, C + \varepsilon]$, this discrete step gives a contradiction on the bound of $C$ with $C - \frac{\min\{\lambda, 1 - \lambda\}}{2}$ as being smaller.

time for a very weird sol We show that we can't have all sufficently large positive integers $n$ create a sum of more than $\frac{n(n+1)}{2}\lambda$. We will define two variables. One, we will call $AC_n$, the "appearence credit", defined by $n\lambda-|A_n|$. How this will function is, as $n$ increases to $n+1$, we gain $\lambda$ appearence credit immediately, then for each $n+1$ we put in $A$, we lose $1$ appearence credit. The other variable is the "sum credit", denoted $SC_n$, defined by $(\sum A_n)-\frac{n(n+1)}{2}\lambda.$ How this will work is, when going from $n$ to $n+1$, we lose $(n+1)\lambda$ sum credit immediately, but we gain back $n+1$ sum credit for each time $n+1$ appears in $A$. Essentially what is happening is, each turn we gain $\lambda$ appearance credit and lose $(n+1)\lambda$ sum credit. Then, we can make any nonnegative number of "exchanges", where we spend 1 appearance credit to gain $n+1$ sum credit. We are essentially trying to show that the appearance credit and sum credit cannot both be nonnegative for all sufficently large $n$. Assume otherwise. Notice that within each turn, the gain/loss in sum credit is $n+1$ times the gain/loss in appearance credit, in the opposite direction. This motivates us to look at the value $$AC_{n+1}+\frac{SC_{n+1}}{n+1},$$which does not change within a turn. For sufficently large $n$, this is a decreasing monovariant, since within each turn it does not change, but when we increase $n$ by 1, this doesn't change or decreases as we are assuming $SC_n$ is nonnegative for sufficiently large $n$. However, consider this, We never want to make "exchanges" unless we are forced to (as in $SC_n$ becomes negative if we do not), since the value of each $AC$ increases as we wait, so performing an unnecessary exchange is dominated by performing the same exchange later. Thus, the optimal strategy is to not make exchanges until $SC_n$ becomes negative if we don't, and then make one exchange (after this $SC_n$ is guaranteed positive as $n+1>(n+1)\lambda$). If we show that even this does not work we would be done. After an exchange is made, we must have $SC_{n+1}\geq (n+1)(1-\lambda)$, since the previous turn it was nonnegative, and it decreased by $(n+1)\lambda$ and the increased by $n+1$. Thus, consider what happens to $$AC_{n+1}+\frac{SC_{n+1}}{n+1}$$at the turn increment right after such an exchange. The act of incrementing the turn counter decreases this monovariant by at least $$SC_{n+1}(\frac{1}{(n+1)(n+2)}),$$which we know is at least $$\frac{1-\lambda}{n+2}.$$ Therefore, right after an exchange, the turn increment immediately following it decreases the monovariant by at least $$\frac{1-\lambda}{n+2}$$ Since we are forced to exchange at least once every approximately $\frac{1}{\lambda}$ turns (it's only important that it has an upper bound not depending on $n$), due to losing $(n+1)\lambda$ sum credit on turn $n$ if we don't, by harmonic series, the sum of $$\frac{1-\lambda}{n+2}$$over all turns that we have to exchange on diverges. Thus, it cannot be forever nonnegative, solved.

$ $