Subset order 50 of $\{1,2,..,99\}$ has two numbers such that their sum is 99

Question

I ran into problem from "Putnam and Beyond" from section about Pigeonhole principle. I was thinking about that problem few hours but unfortunately i was not able to solve it. Also I have found the duplication of this topic but it did not help me since solutions are not quite detailed.

Given $50$ distinct positive integers strictly less than $100$, prove that some two of them sum to $99$.

My efforts: Let $S=\{x_1,x_2,\dots,x_{50}\}\subset \{1,2,\dots, 99\}$ and $x_i+x_j=99$ iff $(x_i,x_j)\in \{(1,98),(2,97),\dots,(49,50)\}$. Here we have $49$ pairs of numbers such that their sum is $99$.

1) What here should be boxes and pigeons?

2) And how to use that all 50 distinct positive integers are strictly less than 100?

Answer 1

Hint:

We divide the positive integers into pairs like: $$\{1,98\}, \{2,97\}, \ldots \{49,50\}$$

These are our $49$ boxes, and as you can see, that if we pick any fifty integers (pigeons), by the pigeonhole principle, we have to pick two integers from the same pair, thus, two numbers sum to $99$.

P.S. It doesn’t make any sense to count 99 as well.

Answer 2

Well, your attempt gives a counter example $$ 1,2,3,4,\dots, 49, 99. $$

But it does not mean that you did it wrong, since the main thoughts for this question is to pick pairs and create the "boxes". I'd rather believe there is a typo on your book.

So here we require that all $50$ numbers are strictly less than $\mathbf{99}$, instead of $100$. Then you've almost got it. Here the $49$ pairs you've found are the "boxes", and the $50$ numbers are the "pigeons". Hence there must be a pair lies in the set of these $50$ numbers by the piegon-hole principle.

UPDATE

The pigeon-hole principle tells us that there are 2 numbers $x_j, x_k $ in the same "box". Since these 2 numbers are distinct, these two form a pair in the box. By the fact that the sum of the pair in each box is $99$ [as you constructed], we have $x_j + x_k = 99$

UPDATE 2

Now I explain it from a different point of view, which is mathematically equivalent to the question.

Suppose you were required to pick out $50$ numbers from $1$ through $98$. Then the pigeonhole principle tells you that you have to pick two number from the same box you've created, which means at least one box is empty now. Equivalently the pair originally lay in this box was picked out by you, and they sum up to $99$.