Pigeonhole Principle question

  1. 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.
     
  2. jcsd
  3. I'd think about consecutive numbers. What is gcd(k, k+1) for positive k?
     
  4. Thanks, but those numbers do not have to be consecutive. Do you have any ideas?
     
  5. Are you sure about that? You have n+1 numbers, and 2n "places" to put them, since none of the numbers can exceed 2n.
     
  6. 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:
     
  7. 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.
     
  8. I finally understood the logic of the question, thank you so very much!
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?