Physics Forums

Physics Forums (http://www.physicsforums.com/index.php)
-   General Math (http://www.physicsforums.com/forumdisplay.php?f=73)
-   -   Pigeonhole Principle question (http://www.physicsforums.com/showthread.php?t=486022)

life is maths Mar31-11 03:50 AM

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.

spamiam Mar31-11 11:06 AM

Re: Pigeonhole Principle question
 
I'd think about consecutive numbers. What is gcd(k, k+1) for positive k?

life is maths Mar31-11 01:53 PM

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

spamiam Mar31-11 04:02 PM

Re: Pigeonhole Principle question
 
Quote:

Quote by life is maths (Post 3221558)
Thanks, but those numbers do not have to be consecutive.

Are you sure about that? You have n+1 numbers, and 2n "places" to put them, since none of the numbers can exceed 2n.

life is maths Apr2-11 06:35 AM

Re: Pigeonhole Principle question
 
Quote:

Quote by spamiam (Post 3221830)
Are you sure about that? You have n+1 numbers, and 2n "places" to put them, since none of the numbers can exceed 2n.

I couldn't understand what you mean by ''2n 'places' to put them''. There are n+1 numbers none of which can exceed 2n. Am I missing something?:confused:

spamiam Apr2-11 07:39 AM

Re: Pigeonhole Principle question
 
Quote:

Quote by life is maths (Post 3224902)
I couldn't understand what you mean by ''2n 'places' to put them''. There are n+1 numbers none of which can exceed 2n. Am I missing something?:confused:

What I'm trying to say is that there must be 2 consecutive numbers in this set, which since gcd(k, k+1) = 1 means that you've found your relatively prime elements. I'll get to the picture I was trying to convey, but here's the result I was getting to:

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.

life is maths Apr6-11 03:59 AM

Re: Pigeonhole Principle question
 
Quote:

Quote by spamiam (Post 3224956)
...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.

I finally understood the logic of the question, thank you so very much!


All times are GMT -5. The time now is 02:07 PM.

Powered by vBulletin Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
© 2014 Physics Forums