Pigeonhole Principle

Apologies for the lack of posts, I have been in Columbia until last Wednesday on a college visit.

Over the past two days, I've worked on the next section of the Methods of Proof chapter in Putnam and Beyond, the Pigeonhole Principle. (Also known as the Box Principle, and many other names). Basically, if you have n holes, and more than n pigeons, at least two pigeons must go in one hole. The primary idea in solving a problem like this is to determine what are the pigeons, and what are the holes.

 I am actually pretty bad at these kind of problems, so I found this section mostly difficult.  I am probably going to continue with it for another day or two. 

Currently, I am definitely lacking in research posts, so I will probably devote most of next week to research.

Here is one of the few problems from the section I have solved. This one is so easy I honestly feel bad about posting it, but I really have nothing better post at this point.

Given 50 distinct positive integers strictly less than 100, prove that some two of

them sum to 99.

Divide the positive integers from 1 to 99 like so:

{1,98}

{2,97}

....

{49,50}

These will be our "holes"

I am assuming if we pick 99, that counts as "summing to 99" otherwise this result is not actually true. (The book's solution seems to agree with me here), so we can basically ignore 99. 

Notice that the remaining integers are all listed here exactly once, there are 49 pairs, and the numbers in a pair sum to 99. If we pick 50 integers (our "pigeons"), by pigeonhole principle, we have to pick 2 from the same pair, which means we have 2 that sum to 99.