Year 12s: what will be the first way you research your future options? >>

Pigeonhole Principal

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! :smile:

(edited 11 years ago)

Reply 1

nohomo

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

Reply 2

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. :biggrin:

Reply 3

nohomo

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. :biggrin:

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?

Reply 4

Brit_Miller

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. :smile:

I've not seen a solution from the marking scheme yet, I just wondered how all of you maths whizzes would approach it.