# Two Pigeonhole Principle Questions

1. Jan 19, 2017

### Of Mike and Men

I've recently switched Universities, and along with that game a textbook change -- however I'm not so sure that's the issue here. These two examples we covered in lecture (which we apparently have a substitute for 6 weeks of this semester who doesn't normally teach discrete 2) and are covered in Kenneth Rosen's book (7ed.) on P. 403. I can include the snippets of their solutions if need be, but I don't find it necessary as I am lost during the first sentence of each solution, as seemed to be the overall consensus of my class as well. If someone could just break down these two examples for me that'd be great. I tried even using concrete numbers and it just doesn't make any sense to me. I've been wracking my brain on these two problems for the last 4 hours to literally no avail....

Lastly, to those who are wondering this is the second portion of the course, so we have covered proof techniques in the last course. I.E. intro to logic, direct proofs, and mathematical induction (if this is at all relevant to how you answer these questions).

Example 1

Show that among any n + 1 positive integers not exceeding 2n there must be an integer that divides one of the other integers.

Example 2
Every sequence of n2 + 1 distinct real numbers contains a subsequence of length n + 1 that is either strictly increasing or strictly decreasing.

Thanks to anyone who has the time/patience.