Question

You randomly select k integers between 1 and 100, inclusive. What is the smallest k that guarantees that at least one pair of the selected integers will sum to 101? Prove your answer.

Answer 1

Answer:

51

Step-by-step explanation:

The possible components to sum up to 101 can only be divided into 2 groups, 1 is larger than 50 and the other is less than or equals to 50

For example

50 + 51 = 101

52 + 49 = 101

60 + 41 = 101

...

99 + 2 = 101

100 + 1 = 101

Therefore, the worst case scenario is to pick all numbers from only 1 group, either all number less than or equal to 50, which there are 50 of them from 1 to 50, or greater than 50, which there are 50 of them from 51 to 100.

So k has to be at least 51 to guarantee that at least one pair of the selected integers will sum to 101