Prove that any subset of six elements of $S=\left\{1,2,...,9 \right\}$ must contain at least two elements whose sum is 10.

Question

Prove that any subset of six elements of $S=\left\{1,2,...,9 \right\}$ must contain at least two elements whose sum is 10.

I thought of using the pigeonhole principle, but I can't think of how to write this proof, I can only think of particular cases.

Let's say I have the subset $A\subset S$, $A=\left\{1,2,3,4,5,6 \right\}$, so there's $6+4=10$, and $5+2+1$ and blah blah blah...

I can't think of a way to "generalize" this... Any ideas?

Answer 1

Make a partition $$\{1,9\}, \{2,8\},\{3,7\},\{4,6\}\{5\}$$ So we have 5 sets(houses) and 6 numbers (pigeons)...

Perhaps this:

If we have set with first $2n-1$ elements than every set with $n$ elements have a pair such that their sum is $2n$