[Brit_Miller]

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!

[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

[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.

[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.

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?

[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. I've not seen a solution from the marking scheme yet, I just wondered how all of you maths whizzes would approach it.

[nohomo]

(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.

[Brit_Miller]

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!