Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Pigeonhole Principle question

  1. Mar 31, 2011 #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. Mar 31, 2011 #2
    I'd think about consecutive numbers. What is gcd(k, k+1) for positive k?
  4. Mar 31, 2011 #3
    Thanks, but those numbers do not have to be consecutive. Do you have any ideas?
  5. Mar 31, 2011 #4
    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. Apr 2, 2011 #5
    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. Apr 2, 2011 #6
    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. Apr 6, 2011 #7
    I finally understood the logic of the question, thank you so very much!
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Pigeonhole Principle question