Results 1 to 3 of 3

Math Help - Pigeon hole-proof

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    7

    Pigeon hole-proof

    You're supposed to show this with the pigeon hole principle.

    Imagine the set {1, 2, ....., 2n}. Chose from this set n+1 different integers. Prove that there is always two integers among the chosen ones whose largest common divisor is 1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Quote Originally Posted by Severus View Post
    You're supposed to show this with the pigeon hole principle.

    Imagine the set {1, 2, ....., 2n}. Chose from this set n+1 different integers. Prove that there is always two integers among the chosen ones whose largest common divisor is 1.
    Hmm, I'll give it a shot, but no promises :/

    Since your set is {1, 2, 3, ... , 2n) You will have 2n elements.
    Let us group every two elements together as such:
    Set A = {{1,2}, {3,4}, {5,6} ... , {2n-1, 2n}}

    Since each element in A contains consecutive integers, then if both integers from any element are chosen there will be two integers among the chosen which have a greatest common divisor of 1.

    As there are 2 integers in each element, there are a total of n elements in this set. Then if you choose n integers, one integer may come from each element. So each element may have 1 integer selected from it. Since you are taking n+1 integers, you must take one more integer, however there are no more empty elements to choose from, so you must choose from one of the elements you have already drawn from. So because there are n elements in A, and you must choose n+1 integers, by the pigeonhole principle you must choose at least two from the same element.

    Thus there will be at least two integers chosen which are consecutive, thus there will be two integers chosen who's greatest common divisor is one.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2008
    Posts
    7
    Thank you, that was usefull.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 17th 2011, 08:44 PM
  2. Pigeon-hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 31st 2011, 06:14 AM
  3. Pigeon Hole Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 18th 2010, 07:53 AM
  4. pigeon-hole
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 02:41 PM
  5. Pigeon hole-proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: February 11th 2008, 09:34 AM

Search Tags


/mathhelpforum @mathhelpforum