You are Here: Home

# Pigeonhole Principal

Announcements Posted on
Take our survey to be in with the chance of winning a £50 Amazon voucher or one of 5 x £10 Amazon vouchers 28-05-2016
1. 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. 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. 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. (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. (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. (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

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

This proof uses the pigeonhole principle, but I don't know what mark it would get on your exam.
7. 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!

## Register

Thanks for posting! You just need to create an account in order to submit the post
1. this can't be left blank
2. this can't be left blank
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
1. Oops, you need to agree to our Ts&Cs to register

Updated: May 4, 2012
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Today on TSR

### Don't be a half-term hermit

How to revise this week and still have a life

Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read here first

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams