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
Talking about ISA/EMPA specifics is against our guidelines - read more here 05-03-2015
  1. 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!
  2. 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
  3. 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.
  4. 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?
  5. 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.
  6. 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.
  7. 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 4, 2012
2015 general election
New on TSR

The secret to exam success

Flex your flow muscle...

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