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)
m (→‎Solution)
 
(9 intermediate revisions by the same user not shown)
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{n(n+1)}{2}\lambda</math>, and for all <math>k>m</math>, <math>S_k>\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>,
Line 13: Line 13:
 
\leq n\lambda
 
\leq n\lambda
 
</cmath>
 
</cmath>
−
also,  
+
Also,  
 
<math>
 
<math>
 
\frac{S_{n}}{n}>\frac{n+1}{2}\lambda
 
\frac{S_{n}}{n}>\frac{n+1}{2}\lambda
Line 25: Line 25:
 
<math>\hdots</math>
 
<math>\hdots</math>
 
<math>
 
<math>
−
\frac{S_{m_1}}{(m+2)(m+1)}>\frac{1}{2}\lambda
+
\frac{S_{m+1}}{(m+2)(m+1)}>\frac{1}{2}\lambda
 
</math>,  
 
</math>,  
 
<math>
 
<math>
 
\frac{S_{m}}{(m+1)m}\leq \frac{1}{2}\lambda
 
\frac{S_{m}}{(m+1)m}\leq \frac{1}{2}\lambda
−
</math>,
 
−
<math>\hdots</math>
 
−
<math>
 
−
\frac{S_{1}}{2\cdot1}\leq \frac{1}{2}\lambda
 
 
</math>.
 
</math>.
  
−
Now, for any <math>n\in\mathbb{N}</math>, we let <math>|\frac{S_n}{(n+1)n}-\frac{1}{2}\lambda|=d_n</math>, then
+
Now, for any <math>n\in\mathbb{N}</math>, we let <math>\frac{S_n}{(n+1)n}-\frac{1}{2}\lambda=d_n</math>, then
 
<cmath>
 
<cmath>
 
\frac{1}{n}\cdot S_n+\sum_{i=1}^{n-1}\frac{S_i}{i(i+1)}
 
\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
+
=n\lambda+(n+1)\cdot d_n+\sum_{i=m+1}^{n-1}d_i+\sum_{i=1}^{m}d_i
 
\leq n\lambda
 
\leq n\lambda
 
</cmath>
 
</cmath>
−
Let <math>\sum_{i=1}^{m}d_i=c</math>, then <math>n\lambda-c<\sum_{i=1}^{n}k_i\leq n\lambda</math>. Dividing both sides by <math>n</math>, <math>\lambda-c/n<\frac{\sum_{i=1}^{n}k_i}{n}\leq \lambda</math>. Taking the limit yields
+
Let <math>\sum_{i=1}^{m}d_i=-c</math> (where <math>c</math> is positive, otherwise we already have a contradiction), then  
 +
<cmath>n\lambda-c<
 +
n\lambda+(n+1)\cdot d_n+\sum_{i=m+1}^{n-1}d_i-c
 +
=\sum_{i=1}^{n}k_i\leq n\lambda</cmath>
 +
Dividing both sides by <math>n</math>, <math>\lambda-c/n<\frac{\sum_{i=1}^{n}k_i}{n}\leq \lambda</math>. Taking the limit yields
 
<math>
 
<math>
 
\lim_{n\to\infty}{\frac{\sum_{i=1}^{n}k_i}{n}}=\lambda
 
\lim_{n\to\infty}{\frac{\sum_{i=1}^{n}k_i}{n}}=\lambda
−
</math>
+
</math>.
 
Observe that this would imply that
 
Observe that this would imply that
 
<cmath>
 
<cmath>

Latest revision as of 20:08, 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< n\lambda+(n+1)\cdot d_n+\sum_{i=m+1}^{n-1}d_i-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=99481"