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 <...") |
(→Problem 6) |
||
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 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}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>. | ||
+ | |||
+ | 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>, | ||
+ | <math>\hdots</math> | ||
+ | <math> | ||
+ | \frac{S_{1}}{2\cdot1}\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>, 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 | ||
+ | <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. |
Revision as of 18:44, 15 December 2018
Problem 6
Consider , and let
be a multiset of positive integers. Let
. Assume that for every
, the set
contains at most
numbers. Show that there are infinitely many
for which the sum of the elements in
is at most
. (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
and
are equivalent, but
and
differ.)
Solution
Proposed by mengmeng142857.
We prove this by contradiction. Suppose that the number that an integer appears in
is
. Let the sum of the elements in
be
. If there are only finitely many
such that
, then by the well ordering principle, there must be a largest
such that
, and for all
,
.
Now, observe that for some ,
also,
,
,
,
,
,
.
Now, for any , we let
, then
Let
, then
. Dividing both sides by
,
. Taking the limit yields
Observe that this would imply that
However, as
is an integer, it is impossible for it to converge to
. This yields the desired contradiction.