Difference between revisions of "2015 USAMO Problems/Problem 6"
(→Solution) |
m (→Solution) |
||
(10 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\ | + | 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, | |
<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_{ | + | \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>. | ||
− | Now, for any <math>n\in\mathbb{N}</math>, we let <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> | <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 | + | =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 < | + | 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 21:08, 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 of times 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
(where
is positive, otherwise we already have a contradiction), 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.