Results are out! Find what you need...fast. Get quick advice or join the chat
Hey! Sign in to get help with your study questionsNew here? Join for free to post

Pigeonhole Principal

Announcements Posted on
Applying to uni this year? Check out our new personal statement advice hub 28-11-2014
    • Thread Starter
    • 5 followers
    Offline

    ReputationRep:
    I understand the principal, but I'm not sure how to prove it correctly, it was the one question I was really unsure of in my January exam and I think it's gonna crop up again!

    "Show that if five integers are selected from the first eight positive integers, then
    there always exists a pair of these five integers whose sum is 9."

    So I would set up a function of X = {x_1, ... x_5},where 1<=x<=9 and Y = {{1,9}, ... {4,5}} and obviously |X|= 5 > |Y| = 4, but I'm not sure how to express this as a proper proof showing that arbitrarily f(x_j) = f(x_k)?

    Thanks!
    • 11 followers
    Offline

    ReputationRep:
    Let X be the set of five numbers selected. If no two of the numbers summed to 9, then only one of 1 and 8 could be present in X, only one of 2 and 7 could be present in X, only one of 3 and 6 could be present in X, and only one of 4 and 5 could be present in X, so X would have at most four numbers, which is a contradiction.

    I'm not sure if this uses the pigeonhole principle very well though
    • Thread Starter
    • 5 followers
    Offline

    ReputationRep:
    That's kinda what I blagged in the January exam and only got something like 6/9 and I'm pretty sure they want me to be more rigorous in this exam.
    • 11 followers
    Offline

    ReputationRep:
    (Original post by Brit_Miller)
    That's kinda what I blagged in the January exam and only got something like 6/9 and I'm pretty sure they want me to be more rigorous in this exam.
    What I posted is a correct proof and is fully rigorous. I'm not sure if it uses the pigeonhole principle properly though. Have you looked online for a marking scheme for this paper?
    • Thread Starter
    • 5 followers
    Offline

    ReputationRep:
    (Original post by nohomo)
    What I posted is a correct proof and is fully rigorous. I'm not sure if it uses the pigeonhole principle properly though. Have you looked online for a marking scheme for this paper?
    I'm not saying it isn't right! I just meant I did something similar last time and got marked down, so I thought maybe there was a way you were supposed to approach the problem other than this. I've not seen a solution from the marking scheme yet, I just wondered how all of you maths whizzes would approach it.
    • 11 followers
    Offline

    ReputationRep:
    (Original post by Brit_Miller)
    I'm not saying it isn't right! I just meant I did something similar last time and got marked down, so I thought maybe there was a way you were supposed to approach the problem other than this. I've not seen a solution from the marking scheme yet, I just wondered how all of you maths whizzes would approach it.
    I think I have an idea of what they'd want. Consider the set

    Y = \left\{ (1,8),(2,7),(3,6),(4,5)\right\}

    In choosing five numbers from 1 to 8, we are choosing five numbers from the pairs in the set Y. Since there are four pairs in Y, by the Pigeonhole principle, we must choose two numbers which occur in the same pair in Y, and these two numbers sum to 9.

    This proof uses the pigeonhole principle, but I don't know what mark it would get on your exam.
    • Thread Starter
    • 5 followers
    Offline

    ReputationRep:
    Yeah that's the structure of the proof I wanted, maybe I'm trying to be too general in the proof and should just point out the obvious!

Reply

Submit reply

Register

Thanks for posting! You just need to create an account in order to submit the post
  1. this can't be left blank
    that username has been taken, please choose another Forgotten your password?
  2. this can't be left blank
    this email is already registered. Forgotten your password?
  3. this can't be left blank

    6 characters or longer with both numbers and letters is safer

  4. this can't be left empty
    your full birthday is required
  1. By joining you agree to our Ts and Cs, privacy policy and site rules

  2. Slide to join now Processing…

Updated: May 5, 2012
New on TSR

Vote for your favourite Christmas film

Win a bundle of Xmas DVDs

Article updates
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.