Pigeonhole Principle question

[life is maths]

Hi, I love the pigeonhole principle subject, but the problem is I'm not very sharp to solve questions easily. 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]

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

 

[life is maths]

Thanks, but those numbers do not have to be consecutive. Do you have any ideas?

 

[spamiam]

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]

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?

 

[spamiam]

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?

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]

...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!