Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2015 USAMO Problems/Problem 6"

(→‎Solution)
(→‎Solution)
Line 5: Line 5:
 
Proposed by mengmeng142857.
 
Proposed by mengmeng142857.
  
−
We prove this by contradiction. Suppose that the number that an integer <math>a</math> appears in <math>A</math> is <math>k_a</math>. Let the sum of the elements in <math>A_n</math> be <math>S_n=\sum_{i=1}^{n}i\cdot k_i</math>. If there are only finitely many <math>n\in\mathbb{N}</math> such that <math>S_n\leq\frac{n(n+1)}{2}\lambda</math>, then by the well ordering principle, there must be a largest <math>m\in\mathbb{N}</math> such that <math>S_m\leq\frac{m(m+1)}{2}\lambda</math>, and for all <math>n>m</math>, <math>S_n>\frac{n(n+1)}{2}\lambda</math>.
+
We prove this by contradiction. Suppose that the number of times that an integer <math>a</math> appears in <math>A</math> is <math>k_a</math>. Let the sum of the elements in <math>A_n</math> be <math>S_n=\sum_{i=1}^{n}i\cdot k_i</math>. If there are only finitely many <math>n\in\mathbb{N}</math> such that <math>S_n\leq\frac{n(n+1)}{2}\lambda</math>, then by the well ordering principle, there must be a largest <math>m\in\mathbb{N}</math> such that <math>S_m\leq\frac{m(m+1)}{2}\lambda</math>, and for all <math>n>m</math>, <math>S_n>\frac{n(n+1)}{2}\lambda</math>.
  
 
Now, observe that for some <math>n>m</math>,
 
Now, observe that for some <math>n>m</math>,

Revision as of 20:55, 15 December 2018

Problem 6

Consider $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\mathbb{N}$, the set $A_n$ contains at most $n\lambda$numbers. Show that there are infinitely many $n\in\mathbb{N}$ for which the sum of the elements in $A_n$ is at most $\frac{n(n+1)}{2}\lambda$. (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

Proposed by mengmeng142857.

We prove this by contradiction. Suppose that the number of times that an integer $a$ appears in $A$ is $k_a$. Let the sum of the elements in $A_n$ be $S_n=\sum_{i=1}^{n}i\cdot k_i$. If there are only finitely many $n\in\mathbb{N}$ such that $S_n\leq\frac{n(n+1)}{2}\lambda$, then by the well ordering principle, there must be a largest $m\in\mathbb{N}$ such that $S_m\leq\frac{m(m+1)}{2}\lambda$, and for all $n>m$, $S_n>\frac{n(n+1)}{2}\lambda$.

Now, observe that for some $n>m$, \[\frac{1}{n}\cdot S_{n}+\frac{1}{n(n-1)}\cdot S_{n-1}+\frac{1}{(n-1)(n-2)}\cdot S_{n-2}+...+\frac{1}{2\cdot1}\cdot S_{1} =\sum_{i=1}^{n}k_i \leq n\lambda\] also, $\frac{S_{n}}{n}>\frac{n+1}{2}\lambda$, $\frac{S_{n-1}}{n(n-1)}>\frac{1}{2}\lambda$, $\frac{S_{n-2}}{(n-1)(n-2)}>\frac{1}{2}\lambda$, $\hdots$ $\frac{S_{m_1}}{(m+2)(m+1)}>\frac{1}{2}\lambda$, $\frac{S_{m}}{(m+1)m}\leq \frac{1}{2}\lambda$.

Now, for any $n\in\mathbb{N}$, we let $\frac{S_n}{(n+1)n}-\frac{1}{2}\lambda=d_n$, then \[\frac{1}{n}\cdot S_n+\sum_{i=1}^{n-1}\frac{S_i}{i(i+1)} =n\lambda+(n+1)\cdot d_n+\sum_{i=m+1}^{n-1}d_i+\sum_{i=1}^{m}d_i \leq n\lambda\] Let $\sum_{i=1}^{m}d_i=c$ (where $c$ is positive, otherwise we already have a contradiction), then $n\lambda-c<\sum_{i=1}^{n}k_i\leq n\lambda$. Dividing both sides by $n$, $\lambda-c/n<\frac{\sum_{i=1}^{n}k_i}{n}\leq \lambda$. Taking the limit yields $\lim_{n\to\infty}{\frac{\sum_{i=1}^{n}k_i}{n}}=\lambda$ Observe that this would imply that \[\lim_{n\to\infty}{k_n} =\lim_{n\to\infty}{\left(\sum_{i=1}^{n}k_i-\sum_{i=1}^{n-1}k_i\right)} =\lim_{n\to\infty}{\left(n\cdot\frac{\sum_{i=1}^{n}k_i}{n}-(n-1)\cdot\frac{\sum_{i=1}^{n-1}k_i}{n-1}\right)} =\lambda\] However, as $k_n$ is an integer, it is impossible for it to converge to $\lambda$. This yields the desired contradiction.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2015_USAMO_Problems/Problem_6&oldid=99472"