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

Homework Help: Pigeonhole principle question

  1. Mar 22, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove that, in any set of n + 1 positive integers (n ≥ 1) chosen from the set {1, 2, . . . 2n}, it must be that two of them are relatively prime (i.e. have no common divisor except 1). ( Hint: two consecutive integers are relatively prime. Make boxes labelled by pairs of consecutive integers. ).
    2. Relevant equations

    pigeonhole

    3. The attempt at a solution
     
  2. jcsd
  3. Mar 23, 2010 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    That's a pretty good hint. What have you tried or what ideas do you have? We aren't here to work it for you.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook