Guaranteed sum
Suppose you randomly select k of the first 2016 positive integers. What is the smallest k that guarantees that at least one pair of the selected integers will sum to 2017?
The answer is 1009.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
2 solutions
Selecting k intergers randomly we can select 1008 and 1009 right.The only pair possible is with these two and it sums up to 2017.So cant 'k' be 2.
Log in to reply
2 doesn't guarantee that sum will add up to 2017. What if you select 45 and 48?
No! If so, then you can't guarantee that you will have exactly 1008 and 1009. You can also have 1,2 or 5,3 etc. which doesn't sum to 2017. So you have to make sure that you pick at least some integers that there exists a pair of the selected integers which sums to 2017. Now think, why didn't we take the pair 2,2015 or 3,2014 and so on?
Log in to reply
The FIRST k elements are being selected, so it's guaranteed that there will exist 1008 and 1009 consecutively
a+b have to sum up to 2016 with a = b. What is the worst case we can select numbers? It's always picking the smallest number. And what is the largest possible sum we can build with a given set? The sum of the two largest elements. k 2 3 . . . 1 0 0 8 1 0 0 9 set { 1 , 2 } { 1 , 2 , 3 } . . . { 1 , 2 , . . . , 1 0 0 7 , 1 0 0 8 } { 1 , 2 , . . . , 1 0 0 8 , 1 0 0 9 } largest sum 1 + 2 = 3 2 + 3 = 5 . . . 1 0 0 7 + 1 0 0 8 = 2 0 1 5 1 0 0 8 + 1 0 0 9 = 2 0 1 7
There exist 2 0 1 6 / 2 = 1 0 0 8 pairs of integers that sum to 2 0 1 7 : ( 1 , 2 0 1 6 ) , ( 2 , 2 0 1 5 ) , … , ( 1 0 0 8 , 1 0 0 9 ) . If only 1 0 0 8 integers are selected, it is possible to select the first 1 0 0 8 positive integers, none of which pairwise sum to 2 0 1 7 . By the pigeonhole principle, selecting at least 1 0 0 8 + 1 = 1 0 0 9 integers guarantees that at least two of the integers will be part of a pair that sums to 2 0 1 7 .