Difference between revisions of "2016 USAJMO Problems/Problem 4"
(Created page with "== Problem == Find, with proof, the least integer <math>N</math> such that if any <math>2016</math> elements are removed from the set <math>{1, 2,...,N}</math>, one can still ...") |
|||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Find, with proof, the least integer <math>N</math> such that if any <math>2016</math> elements are removed from the set <math>{1, 2,...,N}</math>, one can still find <math>2016</math> distinct numbers among the remaining elements with sum <math>N</math>. | + | Find, with proof, the least integer <math>N</math> such that if any <math>2016</math> elements are removed from the set <math>\{1, 2,...,N\}</math>, one can still find <math>2016</math> distinct numbers among the remaining elements with sum <math>N</math>. |
== Solution == | == Solution == | ||
| + | Since any <math>2016</math> elements are removed, suppose we remove the integers from <math>1</math> to <math>2016</math>. Then the smallest possible sum of <math>2016</math> of the remaining elements is <cmath>2017+2018+\cdots + 4032 = 1008 \cdot 6049 = 6097392</cmath> | ||
| + | so clearly <math>N\ge 6097392</math>. We will show that <math>N=6097392</math> works. | ||
| + | <math>\vspace{0.2 in}</math> | ||
| + | |||
| + | <math>\{1,2\cdots 6097392\}</math> contain the integers from <math>1</math> to <math>6048</math>, so pair these numbers as follows: | ||
| + | |||
| + | <cmath>1, 6048</cmath> | ||
| + | |||
| + | <cmath>2, 6047</cmath> | ||
| + | |||
| + | <cmath>3, 6046</cmath> | ||
| + | |||
| + | <cmath>\cdots</cmath> | ||
| + | |||
| + | <cmath>3024, 3025</cmath> | ||
| + | |||
| + | When we remove any <math>2016</math> integers from the set <math>\{1,2,\cdots N\}</math>, clearly we can remove numbers from at most <math>2016</math> of the <math>3024</math> pairs above, leaving at least <math>1008</math> complete pairs. To get a sum of <math>N</math>, simply take these <math>1008</math> pairs, all of which sum to <math>6049</math>. The sum of these <math>2016</math> elements is <math>1008 \cdot 6049 = 6097392</math>, as desired. | ||
| + | |||
| + | <math>\vspace{0.2 in}</math> | ||
| + | |||
| + | We have shown that <math>N</math> must be at least <math>6097392</math>, and that this value is attainable. Therefore our answer is <math>\boxed{6097392}</math>. | ||
Latest revision as of 13:19, 22 April 2016
Problem
Find, with proof, the least integer 
such that if any 
elements are removed from the set 
, one can still find distinct numbers among the remaining elements with sum .
Solution
Since any elements are removed, suppose we remove the integers from 
to . Then the smallest possible sum of of the remaining elements is ![\[2017+2018+\cdots + 4032 = 1008 \cdot 6049 = 6097392\]](http://latex.artofproblemsolving.com/a/b/e/abeead454a89186cd1d6af57c71a8019d30767bc.png)
so clearly 
. We will show that 
works.
contain the integers from to 
, so pair these numbers as follows:
![\[1, 6048\]](http://latex.artofproblemsolving.com/a/b/6/ab66bc566d13151d33304ea2c40166e470cb01bb.png)
![\[2, 6047\]](http://latex.artofproblemsolving.com/c/6/e/c6ef021d429b79d834f6d076d558c3a769be6f32.png)
![\[3, 6046\]](http://latex.artofproblemsolving.com/8/9/0/8901884ec57945be9e2feebd5b5b294bdefa2056.png)
![\[\cdots\]](http://latex.artofproblemsolving.com/c/e/2/ce26e72ef1985f46ac9b2fedbe0879501540c94c.png)
![\[3024, 3025\]](http://latex.artofproblemsolving.com/2/5/3/253f3092858b3421ad07db453ea7b98714afd4e7.png)
When we remove any integers from the set 
, clearly we can remove numbers from at most of the 
pairs above, leaving at least 
complete pairs. To get a sum of , simply take these pairs, all of which sum to 
. The sum of these elements is 
, as desired.
We have shown that must be at least 
, and that this value is attainable. Therefore our answer is 
.
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
See also
| 2016 USAJMO (Problems • Resources) | ||
| Preceded by Problem 3 |
Followed by Problem 5 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAJMO Problems and Solutions | ||
