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}$.