Answer to Question #306325 in Discrete Mathematics for kasish

Question

 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?

Answer 1

1)k is greater than 1008 because we can take the first k and the maximum sum will not exceed 1007+1008=2015.

2) k = 1009

let's break the numbers into pairs that will give the sum 2017. ((1,2016),(2,2015),...,(1008,1009)), as you can see there are only 1008 such pairs, then according to the Direchle principle, if we take 1009, then at least one pair will be which satisfies the condition.