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 14:19, 22 April 2016

Problem

Find, with proof, the least integer $N$ such that if any $2016$ elements are removed from the set $\{1, 2,...,N\}$, one can still find $2016$ distinct numbers among the remaining elements with sum $N$.


Solution

Since any $2016$ elements are removed, suppose we remove the integers from $1$ to $2016$. Then the smallest possible sum of $2016$ of the remaining elements is \[2017+2018+\cdots + 4032 = 1008 \cdot 6049 = 6097392\] so clearly $N\ge 6097392$. We will show that $N=6097392$ works.

$\vspace{0.2 in}$

$\{1,2\cdots 6097392\}$ contain the integers from $1$ to $6048$, so pair these numbers as follows:

\[1, 6048\]

\[2, 6047\]

\[3, 6046\]

\[\cdots\]

\[3024, 3025\]

When we remove any $2016$ integers from the set $\{1,2,\cdots N\}$, clearly we can remove numbers from at most $2016$ of the $3024$ pairs above, leaving at least $1008$ complete pairs. To get a sum of $N$, simply take these $1008$ pairs, all of which sum to $6049$. The sum of these $2016$ elements is $1008 \cdot 6049 = 6097392$, as desired.

$\vspace{0.2 in}$

We have shown that $N$ must be at least $6097392$, and that this value is attainable. Therefore our answer is $\boxed{6097392}$.


The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

See also

2016 USAJMO (ProblemsResources)
Preceded by
Problem 3
Followed by
Problem 5
1 2 3 4 5 6
All USAJMO Problems and Solutions