Pigeon hole principle sum of integers?

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?

I have to use the pigeon hole principle to solve the problem. My attempt at the solution is to choose $k=51$ integers from $1$ to $51$. The pair $50$ and $51$ add up to $101$. My question is why would I start at 1? Could I just start at $k = 50$ and stop at $51$ and I have my sum that adds up to $101$. Other pairs if I started at $49$ and stopped at $52$ I could still choose $49$ and $52$ and that would still add up to $101$. $k$ would be $4$ integers instead of $2$. From my reasoning the smallest amount of $k$ integers I would have to pick would be two? I still don't understand how I would apply the pigeon hole principle here if I can start from fifty. Any help would be appreciated.

Answer 1

First off, your method of choosing some numbers is incorrect. $50$ and $51$ do add to $101$, but if $k=2$, then the question would say that whatever two numbers we pick, they would sum to $101$. But if we say, chose $1$ and $2$, these clearly don't add to $101$. What we want is no matter which $k$ numbers we pick, we can find two that sum to $101$.

The best way to think about this is to think not of individual numbers, but of pairs.

What I mean by this, is instead of $100$ numbers from $1$ to $100$, we now have $50$ pairs $$\{(1,100), (2,99), (3,98), ..., (50,51) \}$$ And now, it should become apparent that in order to choose no pairs that sum to $101$, we must choose a number from each pair at most once. Thus, when we choose numbers from $51$ pairs, by pidgeonhole principle, we will have chosen both numbers from some pair, and thus have two numbers adding to $101$. Hope that helps!