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 06:53 AM.