Guarantee random pair from subset adds up to x

Question

Suppose I take n numbers from the set S = {2, 4, 6, ..., 50}. How big does n have to be in order to guarantee that, among the numbers I take, some pair will add to 42?

I'm very confused on how to do this problem. I tried 42/2 which is 21. Then since 20 and 22 are the closest pair to that number in the set, I divided the larger number by 2 and got 11. However, the answer appears to be 16 and I'm not sure why. The professor did not explain this question or the concept and I can't find why this is. Can anyone please help clear the question/answer and why it is?

Answer 1

Numbers from $42$ to $50$ are useless, so let us see how many we need from $2$ to $40$, and add $5$.

Call two even numbers from $2$ to $40$ buddies if they add up to $42$. There are $10$ pairs of buddies. So if we pick $11+5$ numbers, we will be sure to have a pair of buddies. And it is easy to see that if we are unlucky, $15$ numbers are not enough.

Answer 2

Think of it this way: If you put together a list/group with $2$ in it, you couldn't have $40$ in it; likewise, $4$ and $38$, $6$ and $36$ etc. If you list these out, you realize that if you only take one half of these pairs you will never make $42$ from any pair in your pile; as well, the numbers from $42$ up are 'safe' since they can't be paired with anything to equal $42$.

So if you had a list like this: $\{2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 42, 44, 46, 48, 50\}$ You'd be stuck: Add any other remaining number picked from the list, and there would be a pair that add up to $42$ (remaining ones are $\{22, 24, 26, 28, 30, 32, 34, 36, 38, 40\}$) Since that first list has $15$ in it, and there's no way you could add any more without creating a pair adding to $42$, you're done - add one and you have your guarantee of $16$ items.