2016 Sets

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

806 posts

#1 h Apr 20, 2016, 9:30 PM • 11 Y

Y by wu2481632, Davi-8191, samrocksnature, HWenslawski, math31415926535, jhu08, Adventure10, Mango247, ItsBesi, cubres, NicoN9

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

This post has been edited 1 time. Last edited by NormanWho, Apr 20, 2016, 9:31 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

nosaj

2008 posts

nosaj

#2 h Apr 20, 2016, 9:32 PM • 9 Y

Y by futurewriter, wu2481632, myh2910, russellk, HWenslawski, jhu08, megarnie, Adventure10, NicoN9

I got $N = 1008 \cdot 6049 = 6097392$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

jam10307

471 posts

jam10307

#3 h Apr 20, 2016, 9:32 PM • 5 Y

Y by wu2481632, suvamkonar, jhu08, Adventure10, NicoN9

I got $6097392,$ basically match up pairs to make $6049$ and gg.

^sniped

This post has been edited 1 time. Last edited by jam10307, Apr 20, 2016, 9:33 PM
Reason: asfd

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

wu2481632

4239 posts

wu2481632

#4 h Apr 20, 2016, 9:32 PM • 2 Y

Y by jhu08, Adventure10

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NormanWho

806 posts

NormanWho

#5 h Apr 20, 2016, 9:33 PM • 3 Y

Y by jhu08, Adventure10, Mango247

nosaj wrote:

I got $N = 1008 \cdot 6049 = 6097392$ .

I got the same answer

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hwl0304

1840 posts

hwl0304

#6 h Apr 20, 2016, 9:34 PM • 3 Y

Y by jhu08, Adventure10, Mango247

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

This post has been edited 1 time. Last edited by hwl0304, Apr 20, 2016, 9:35 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

FlakeLCR

1791 posts

FlakeLCR

#7 h Apr 20, 2016, 9:34 PM • 3 Y

Y by bestwillcui1, Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tommy2002

81 posts

Tommy2002

#8 h Apr 20, 2016, 9:34 PM • 2 Y

Y by Adventure10, Mango247

Proved this was the minimum, didn't prove it actually worked.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathwizard888

1635 posts

mathwizard888

#9 h Apr 20, 2016, 9:34 PM • 3 Y

Y by Adventure10, Mango247, NicoN9

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathmaster2012

636 posts

mathmaster2012

#10 h Apr 20, 2016, 9:35 PM • 2 Y

Y by Adventure10, Mango247

solution is just pair up mumbers summing to 6049 and noting that 3024-2016=1008 pairs remain alve

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

room456

146 posts

room456

#11 h Apr 20, 2016, 9:35 PM • 1 Y

Y by Adventure10

how many points for finding 1008(6049) and proving that anything less than that works but not showing it is achievable?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

macandcheese

70 posts

macandcheese

#12 h Apr 20, 2016, 9:36 PM • 1 Y

Y by Adventure10

Any points for saying that 6097392 is the smallest possible value without showing it worked?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

hwl0304

1840 posts

hwl0304

#13 h Apr 20, 2016, 9:36 PM • 1 Y

Y by Adventure10

probably 0-1.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

bestwillcui1

2735 posts

bestwillcui1

#14 h Apr 20, 2016, 9:36 PM • 1 Y

Y by Adventure10

1 point.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NormanWho

806 posts

NormanWho

#15 h Apr 20, 2016, 9:37 PM • 1 Y

Y by Adventure10

I used pigeonhole to prove achievable.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Infinity_Integral

306 posts

Infinity_Integral

#96 h Sep 7, 2023, 1:38 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peace09

5417 posts

peace09

#97 h Oct 8, 2023, 12:34 AM

Y by

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#98 h Oct 27, 2023, 11:06 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

794 posts

shendrew7

#99 h Dec 16, 2023, 9:37 PM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peppapig_

280 posts

peppapig_

#100 h Mar 13, 2024, 2:47 AM

Y by

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

This post has been edited 1 time. Last edited by peppapig_, Mar 13, 2024, 2:50 AM
Reason: Grammar

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

196 posts

de-Kirschbaum

#101 h Apr 12, 2024, 7:44 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Markas

105 posts

Markas

#102 h May 6, 2024, 8:37 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

631 posts

eg4334

#103 h Oct 10, 2024, 2:05 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megahertz13

3182 posts

megahertz13

#104 h Nov 3, 2024, 1:50 AM • 1 Y

Y by kilobyte144

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

This post has been edited 3 times. Last edited by megahertz13, Nov 3, 2024, 1:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Siddharthmaybe

106 posts

Siddharthmaybe

#105 h Nov 20, 2024, 9:04 PM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

D4N13LCarpenter

13 posts

D4N13LCarpenter

#106 h Jan 10, 2025, 7:19 PM • 1 Y

Y by Vahe_Arsenyan

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

gladIasked

648 posts

gladIasked

#107 h Feb 21, 2025, 2:44 AM

Y by

we are so back

The answer is $\boxed{1008\cdot 6049}$ . The lower bound $N\ge 2017+2018+\dots + 4032=1008\cdot 6049$ clearly follows from removing $1, 2, \dots, 2016$ . To show that $1008\cdot 6049$ works, take the pairs $(1, 6048), (2, 6047), \dots, (3024, 3025)$ . No matter how we remove the $2016$ numbers, we will have at least $3024-2016=1008$ complete pairs remaining. This allows us to find $1008\cdot 2=2016$ remaining numbers summing to $1008\cdot 6049$ . $\blacksquare$

This post has been edited 1 time. Last edited by gladIasked, Feb 21, 2025, 2:44 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

peace09

5417 posts

peace09

#108 h Feb 21, 2025, 3:27 AM • 2 Y

Y by 1237542, imagien_bad

Quote:

we are so back

you got this

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ItsBesi

142 posts

ItsBesi

#109 h Mar 14, 2025, 6:18 PM

Y by

Solved this on 20.08.2024 but I am posting it for storage

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

akliu

1795 posts

akliu

#110 h Apr 2, 2025, 4:12 PM

Y by

Claim: The least integer $N$ is at least $N = 1008 \cdot 6049 = 6097392$ .

Proof:
Remove the numbers $1$ to $2016$ from the set. Any $2016$ numbers left will have a sum that's at least $2017+\dots+4032 = 1008 \cdot 6049 = 6097392$ , so clearly $N < 6097392$ doesn't work. $\square$

We now prove attainability of $N = 6097392$ . There are $3024$ pairs of integers in the form $k$ and $6049-k$ that sum to $6049$ . We can remove at most one number from $2016$ of these pairs. However, we have at least $1008$ of these pairs left, and we can choose $1008$ of these pairs, or $2016$ numbers in total, with a total sum of $6097392$ , as desired.

Z K Y