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"

(Created page with "===Problem 6=== Consider <math>0<\lambda<1</math>, and let <math>A</math> be a multiset of positive integers. Let <math>A_n=\{a\in A: a\leq n\}</math>. Assume that for every <...")
 
m (→‎Solution)
 
(12 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
===Problem 6===
 
===Problem 6===
 
Consider <math>0<\lambda<1</math>, and let <math>A</math> be a multiset of positive integers. Let <math>A_n=\{a\in A: a\leq n\}</math>. Assume that for every <math>n\in\mathbb{N}</math>, the set <math>A_n</math> contains at most <math>n\lambda</math>numbers. Show that there are infinitely many <math>n\in\mathbb{N}</math> for which the sum of the elements in <math>A_n</math> is at most <math>\frac{n(n+1)}{2}\lambda</math>. (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 <math>\{1, 2, 3\}</math> and <math>\{2, 1, 3\}</math> are equivalent, but <math>\{1, 1, 2, 3\}</math> and <math>\{1, 2, 3\}</math> differ.)
 
Consider <math>0<\lambda<1</math>, and let <math>A</math> be a multiset of positive integers. Let <math>A_n=\{a\in A: a\leq n\}</math>. Assume that for every <math>n\in\mathbb{N}</math>, the set <math>A_n</math> contains at most <math>n\lambda</math>numbers. Show that there are infinitely many <math>n\in\mathbb{N}</math> for which the sum of the elements in <math>A_n</math> is at most <math>\frac{n(n+1)}{2}\lambda</math>. (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 <math>\{1, 2, 3\}</math> and <math>\{2, 1, 3\}</math> are equivalent, but <math>\{1, 1, 2, 3\}</math> and <math>\{1, 2, 3\}</math> differ.)
 +
 +
===Solution===
 +
Proposed by mengmeng142857.
 +
 +
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>,
 +
<cmath>
 +
\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
 +
</cmath>
 +
Also,
 +
<math>
 +
\frac{S_{n}}{n}>\frac{n+1}{2}\lambda
 +
</math>,
 +
<math>
 +
\frac{S_{n-1}}{n(n-1)}>\frac{1}{2}\lambda
 +
</math>,
 +
<math>
 +
\frac{S_{n-2}}{(n-1)(n-2)}>\frac{1}{2}\lambda
 +
</math>,
 +
<math>\hdots</math>
 +
<math>
 +
\frac{S_{m+1}}{(m+2)(m+1)}>\frac{1}{2}\lambda
 +
</math>,
 +
<math>
 +
\frac{S_{m}}{(m+1)m}\leq \frac{1}{2}\lambda
 +
</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
 +
<cmath>
 +
\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
 +
</cmath>
 +
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>
 +
\lim_{n\to\infty}{\frac{\sum_{i=1}^{n}k_i}{n}}=\lambda
 +
</math>.
 +
Observe that this would imply that
 +
<cmath>
 +
\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</cmath>
 +
However, as <math>k_n</math> is an integer, it is impossible for it to converge to <math>\lambda</math>. This yields the desired contradiction.

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"