Hi, I love the pigeonhole principle subject, but the problem is I'm not very sharp to solve questions easily:uhh:. I'm stuck with this one:(adsbygoogle = window.adsbygoogle || []).push({});

Show that in any set of n+1 positive integers not exceeding 2n, there must be two that are relatively prime.

I tried mathematical induction, but I couldn't finish it. Say n=2, and we have n+1= 3 integers not exceeding 2n=4. It is 1, 2 and 3. It's okay for the base case. Then let's assume it holds for n=k, integers smaller than 2k. Then we add another number so that we have k+1 numbers and they are smaller than 2k+2. How can I prove that those numbers are relatively prime? Is there an easier and more practical way to solve this? Thank you for any help.

**Physics Forums - The Fusion of Science and Community**

# Pigeonhole Principle question

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Pigeonhole Principle question

Loading...

**Physics Forums - The Fusion of Science and Community**