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$.
Problem
Source: 2016 USAJMO 4
Tags: AMC, USA(J)MO, USAJMO, 2016 USAJMO, Sets
21.04.2016 00:32
I got $N = 1008 \cdot 6049 = 6097392$.
21.04.2016 00:32
I got $6097392,$ basically match up pairs to make $6049$ and gg. ^sniped
21.04.2016 00:32
Ugh I got this but couldn't figure out how to prove it 2 or 6? I put down some random stuff about induction I think ugh
21.04.2016 00:33
nosaj wrote: I got $N = 1008 \cdot 6049 = 6097392$. I got the same answer
21.04.2016 00:34
the answer is 6097392 i had kinda inductive thing base is 1-2016 are removed and casework on how the removed numbers change hopefully 7
21.04.2016 00:34
wu2481632 wrote: Ugh I got this but couldn't figure out how to prove it 2 or 6? I put down some random stuff about induction I think ugh 0
21.04.2016 00:34
Proved this was the minimum, didn't prove it actually worked.
21.04.2016 00:34
jam10307 wrote: I got $6097392,$ basically match up pairs to make $6049$ and gg. ^sniped Yea that's what I did, pretty easy for a #4 in my opinion.
21.04.2016 00:35
solution is just pair up mumbers summing to 6049 and noting that 3024-2016=1008 pairs remain alve
21.04.2016 00:35
how many points for finding 1008(6049) and proving that anything less than that works but not showing it is achievable?
21.04.2016 00:36
Any points for saying that 6097392 is the smallest possible value without showing it worked?
21.04.2016 00:36
probably 0-1.
21.04.2016 00:36
1 point.
21.04.2016 00:37
I used pigeonhole to prove achievable.
21.04.2016 00:41
oops maybe I did this stupidly. Let $C=6097392$. Call the $2016$ elements we will find $x_1,x_2,\cdots x_{2016}$. For $1\leq i\leq 2014$, let $x_i$ be the smallest element you can make it. Note that \[x_1+x_2+\cdots +x_{2014}\leq C-4031-4032=C-8063,\]so $x_{2015}+x_{2016}\geq 8063$. Let the sum of the remaining two elements be $r$. Now pair things off like $\{1,r-1\},\{2,r-2\}\cdots \{4031,r-4031\}$ (allowed since $r\geq 8063$). The $2016$ removed elements uses up at most $2016$ of these sets, and the $2014$ already chosen element uses up at most $2014$ more. However, there still is at least $4031-2016-2014=1$ of these sets which hasn't been used. so use it to find $x_{2015}$ and $x_{2016}$. edit: the $6049$ solution is much nicer than this, I guess.
21.04.2016 01:43
I thought this question was really easy (this is coming from someone who got a 0 on Day 1 btw, though tbf I spent the entire time on #1). Proving that anything less than 1008x6049 doesn't work is trivial (1008x6049 = 2017+2018+...+4032), and noticing that there are 3024 = 1008+2016 pairs of 6049 isn't too hard either. Fairly nice problem.
21.04.2016 01:50
Does this solution work? Note that the set $\{2017,\ 2018,\cdots,\ 4032\}$ works for $N=1008*6049$ given that $\{1,\ 2,\cdots,\ 2016\}$ were removed, and that $N$ is the minimal $N$ that works. We claim that $N=1008\cdot 6049$ is indeed valid. If $\{1,\ 2,\cdots,\ 2016\}$ was replaced with any other subset of $\{4032,\ 4033,\cdots,\ N\}\cup \{1,\ 2,\cdots,\ 2016\},$ the same set would trivially hold. Now assume that an element $b_1\in \{2017,\ 2018,\cdots,\ 4032\}$ is removed. If $b_1\neq 4032$ is removed and replaced with $a_1\in \{1,\ 2,\cdots,\ 2016\},$ then we can simply replace $4032$ with $4032+b_1-a_1.$ If $b_2=4032$ is also replaced with $a_2 \in \{1,\ 2,\cdots,\ 2016\},$ we replace $4031$ with $4031+b_1-a_1+b_2-a_2.$ We continue this algorithm if necessary (i.e. when numbers closer and closer to $4032$ are removed), replacing $b_n$ with $b_n+\sum_{i=1}^{k-1}(b_i-a_i).$ Clearly all of the elements will be distinct, and it remains to show that the largest such element is actually an element of $\{1,\ 2,\ 3,\cdots,\ N\}.$ Evidently, $b_m<b_n$ whenever $m<n,$ so our inequality becomes $\sum_{i=1}^{2016}(b_i-a_i)=1008*6049-1008*2017=1008*4032<1008*6049,$ so the largest possible element is always less than $N,$ as desired. Also, will I lose points for not expanding out $1008*6049$?
21.04.2016 01:53
Generic_Username wrote: Also, will I lose points for not expanding out $1008*6049$? Doubt it. I even left it as $2017+2018+\cdots +4032$.
21.04.2016 01:54
Thank god this question saved me from getting 0 on JMO
05.08.2023 03:15
Notice if you delete the extremal 1,2,...,2016 you get 2017,2018,... so it must be at least 2017+2018+...+4032=1008*6049. In these types of problems you always want to separate the elements into groups to use some sort of pigeonhole. Indeed, noticing 2016=1008*2 we can split the numbers up into pairs that sum up to 6049, and show that there must be at least 1008 pairs remaining, from which those 1008 pairs would sum up to 6049*1008. Separate them into (1,6048),(2,6047),...,(3024,3025); deleting 2016 of them makes 1008 pairs, which sum to 6049*1008.
05.08.2023 19:20
07.08.2023 19:38
Consider the case when the numbers $1,2,3,\dots,2016$ are deleted. The minimum value of $N$ must be $2017+\dots+4032=1008\cdot 6049$. We now group some terms into: \[(1,6048),(2,6047),\dots,(3024,3025),\]each with sum $6049$. Notice that if we take any $2016$ terms out, we must be left with at least $1008$ of these ordered pairs. Thus, these pairs must be able to form a sum of $1008\cdot 6049$, implying that the least value of $N$ is $1008\cdot 6049$.
09.08.2023 20:00
First, if the first $2016$ integers are removed from the list, then we must have $2017 + 2018 +\cdots+ 4032 \leq n$, giving $n\geq 6049\cdot 1008$. Now, we will show that $N = 6049 \cdot 1008$ in fact works. Consider the pairs $(1,6038), (2,6037),\ldots, (3024,3025)$ where each of the $3024$ pairs have numbers that sum to $6049$. Now, we will call a pair usable if neither of the numbers in them are removed, and unusable otherwise. When $2016$ numbers are removed from the list, at maximum, $2016$ of these pairs become unusable. So, there are at least $3024 - 2016 = 1008$ usable pairs, so we are able to select the $2016$ numbers from $1008$ usable pairs, and their sum is $6049\cdot 1008$, as desired.
07.09.2023 04:38
We claim the minimum $n$ is $2016^2+1008\cdot2017$. Note that anything below that does not work, since removing $1,2,3,...,2016$ causes any sum of $2016$ distinct numbers to exceed $n$. If we choose $2016^2+1008\cdot2017$, the following algorithm always produces a solution. Suppose $x$ numbers from $1,2,3,...,4030$ are removed. Then we choose the first $2014$ not removed numbers, giving a sum of at most $2014x+1007\cdot2015$ Then $a+b\geq7+2014(2020-x)$. WLOG let $a<b$, then $x+2015\leq a\leq3+1007(2020-x)$ under the worst case (least number of choices for $a$) There are $3+1007\cdot2018-1008x$ pairs of $(a,b)$ at least, which is more than $2016-x$. So at least 1 pair have both numbers not removed, giving a valid solution. Thus $2016^2+1008\cdot2017$ works, and is the minimum possible answer. Full proof here: https://infinityintegral.substack.com/p/usajmo-2016-contest-review
08.10.2023 03:34
28.10.2023 02:06
We claim the answer is $N-1008 \cdot 6049 = \boxed{6097392}$. If $N<6097392$, removing $1,2,\dots, 2016$, we get that the minimum sum is greater than $N$, a contradiction. Now, we show that $N=6097392$ is achievable. There are $3024$ unordered pairs with sum $6049$, and there can only be max $2016$ of those pairs removed, leaving $1008$ of them. Those $1008$ pairs add up to $N$.
17.12.2023 00:37
Our answer is $2017+2018+\ldots+4032=\boxed{1008 \cdot 6049}$. Note that we cannot go any lower; otherwise our condition cannot be satisfied when removing $1,2, \ldots, 2016$. We see this value works as we can form the 3024 pairs \[(1,6048), (2,6047), \ldots, (3024,3025),\] with sum 6049, of which at least 1008 are completely preserved after removing 2016 elements. This forms our subset of 2016 integers summing to $1008 \cdot 6049$. $\blacksquare$
13.03.2024 05:47
I claim that the answer is $6097392$ (hopefully I typed that right, it's supposed to be $1008*6049$). Note that our sum of $2016$ must be at least \[2017+2018+\dots+4032=1008*6049,\]which we need when we remove the positive integers from $1$ to $2016$, inclusive. This implies that $N$ is at least $1008*6049$, and $N$ cannot be any smaller, otherwise if we remove $1$, $2$, $\dots$, $2016$, there don't even exist $2016$ distinct positive integers summing to $N$. Now, I claim that we can always find $2016$ distinct numbers in the set that sum to $N$. This is because there are $3024$ pairs summing to $6049$, and they are $(1,6048)$, $(2,6047)$, $\dots$, $(3024,3025)$. By taking away $2016$ numbers from the big set, we can "destroy" at most $2016$ of these $3024$ pairs, which leaves at least $1008$ full pairs left. If we take all of the numbers from any $1008$ remaining "full" pairs, we get $1008$ pairs of distinct numbers that sum to $6049$ each, for a total of $1008*6049$, or $N$, finishing the problem. C: *Note: In general, if we remove $2k$ numbers and are looking for $2k$ remaining that sum to $N$, using a similar argument, we can prove that the smallest possible value of $N$ is $6k^2+k$, which is also just the sum of the numbers from $2k+1$ to $4k$.
12.04.2024 22:44
We claim that the answer is $6097392$, which is $2017+....+4032$. This is the minimal value of $N$ as we could remove $1,...,2016$ from the set and this is the smallest sum we can get from the remaining elements. Now we prove this satisfies the condition. We note that there are $3024$ pairs of numbers summing up to $6049$, $(1,6048), (2,6047),...,(3024,3025)$. Thus, if we take away any 2016 elements, there will be at least $3024-2016=1008$ such pairs left in the set, which allows us to sum $2016$ distinct elements up to $6097392$.
06.05.2024 11:37
$N \geq 2017+2018+ \cdots + 4032 = 1008.6049$, otherwise our condition can't be satisfied, if we remove $1,2, \cdots, 2016$. Since we got a bound for N, now we need to show it works for this N. We see this value works as we can form the 3024 pairs:$(1,6048), (2,6047), \cdots, (3024,3025)$ with sum 6049, of which at least 1008 are completely preserved after removing 2016 elements. This forms our subset of 2016 integers summing to $1008.6049$ as always possible $\Rightarrow$ N = 1008.6049.
10.10.2024 05:05
The answer is $N = 2017+2018 + \dots + 4032$. To see why nothing lower works consider removing $1, 2, \dots 2016$. To see why N works, manipulate $N = 1008 \cdot 6049$. Pair up the terms into $(1, 6048), (2, 6047), \dots (3024, 3025)$. We can only remove $2016$ pairs leaving us with $1008$ left still. So just use those and we are done.
03.11.2024 04:50
The answer is $N = \boxed{2017+2018+\dots+4032 = 1008\cdot 6049}$. This works: take the pairs $(1,6048), (2, 6047), \dots, (3024, 3025)$. There are at least $1008$ full pairs after $2016$ elements are removed. These $1008$ full pairs sum to $N$. To prove that $N$ is minimal, remove the elements $1$,$2$,$3$,$\dots$, $2016$.
21.11.2024 00:04
We claim that the minimum value of $N$ is $6097392$ Assume we delete the first $2016$ naturals, then the minimum most sum for $N = 2017 + 2018..... + 4031 + 4032$ which is $1008*6049$ So we get that $N \ge 1008*6049$ Now we provide a construction for $N = 1008*6049$ Consider the pairs $(1,6048), (2,6047) ,............, (3024, 3026)$ Now we can choose any $1008$ of these pairs and consider a pair "corrupted" if any one or two of its elements are deleted. Else consider it "normal". Then there are always at least $1008$ normal pairs (when all the $2016$ deletions are used to corrupt a pair), then taking all the elements and summing them all we get $N = 1008*6049 = 6097392$ and so we are done..
10.01.2025 22:19
Let's start by proving an upper bound on N Claim 1 $N\geq 2017+2018+\cdots+4032$ Proof Notice that if the numbers $\{1,2,\dots ,2016\}$ are removed than the least sum is $$2017+2018+\cdots+4032.$$Just like we wanted. I now claim that $N=2017+2018+\cdots +4032$ works. To prove this consider the pairs: $$\{1, 6048\}, \; \{2,6047\}, \dots, \{3024,3025\}.$$Regardless of which $2016$ elements of $\{1, 2, \dots , N\}$ are deleted, at least $3024 - 2016 = 1008$ of these pairs have both elements remaining. Since each pair has sum 6049, we can take these pairs to be the desired numbers.