Pigeonhole Principle question
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:
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. 
Re: Pigeonhole Principle question
I'd think about consecutive numbers. What is gcd(k, k+1) for positive k?

Re: Pigeonhole Principle question
Thanks, but those numbers do not have to be consecutive. Do you have any ideas?

Re: Pigeonhole Principle question
Quote:

Re: Pigeonhole Principle question
Quote:

Re: Pigeonhole Principle question
Quote:
Let S be our set of n+1 numbers that we will choose. For contradiction, we'll try to choose them so that there aren't any numbers that are relatively prime. Then all of our numbers have to have a common divisor greater than 1, which we call d. Since we have a constraint on how big our numbers may be, let's make d as small as possible: d=2. So we choose our first n numbers: 2, 4, 6, ..., 2n. However, now we must choose the (n+1)^{st} number and we realize it can't be done. Any choice we make will result in a choice of 2 consecutive numbers, which will be relatively prime. Sorry, if my comment was a little cryptic. Here's how I was visualizing it. You have 2n cups numbered from 1 to 2n and arranged in order and n+1 balls. You're trying to arrange these n+1 balls so that you never have two consecutive cups with balls in them. You put the first n balls in cups 2, 4, 6, ..., 2n, but then you are left with 1 remaining ball and no cup in which to put it without having two consecutive cups with balls in them. 
Re: Pigeonhole Principle question
Quote:

All times are GMT 5. The time now is 06:25 AM. 
Powered by vBulletin Copyright ©2000  2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums