2016 USAJMO Problems/Problem 4

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.

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

Page

Toolbox

Search

2016 USAJMO Problems/Problem 4

Problem

Solution

See also