A question on counting

Question

I'm having difficulty answering (Qb iii)

Question:

(a) Write an expression for the number of sets S which contain 10 elements, each of which is an integer between 1 and 20.

A: There are ${20 \choose 10}$ ways of selecting 10 integers from 1 to 20 where repetition is not allowed and order doesn't matter. If we consider each of these ways a set then the number of set which contain 10 element, each of which is an integer between 1 and 20 is ${20 \choose 10}$.

(b) Let S be a set with the properties described in (a). (i) How many ways are there to order the members of S?

A: There are 10! ways to order the members of S.

(ii) How many subsets of S have size two?

A: There are ${10 \choose 2}$ subsets of size 2.

(iii) For a non-empty subset X ⊆ S, let t(X) denote the sum of the members of X. Prove that there must be distinct subsets A,B ⊆ S, each of size two, such that t(A) = t(B). (Hint: what are the possible values of t(A) and t(B)?)

Where I am at so far

I realised the following:

Consider 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20.

I realised that if you pick any two number say 5 and 13 then

5 + 13 = 18,

6 + 12 = 18,

7 + 11 = 18 etc.

But that's really all I've realised.

Answer 1

Even more explicit hint... the smallest possible value of $t(A)$ would happen when the subset is $\{1,2\}$ since this is the set using the two smallest available elements while the largest possible value of $t(A)$ would happen when the subset is $\{19,20\}$ since this is the set using the two largest available elements.

The possible outcomes of $t(A)$ are then $3,4,5,\dots,37,38,39$

You correctly noted however that there are $\binom{10}{2}=45$ distinct two-element subsets of $S$ however

And if we compare the number of possible two-element subsets of $S$ to the number of possible values of $t(A)$ we see that one is larger than the other which means...

Answer 2

New proof:

Observe that {1, 2} will have the smallest sum which is 3 and {19, 20} will have the largest sum which is 39.

Now any 2-subset of S will be greater than or equal to 3 and less than or equal to 39. Since we have 45 2-subsets of S and only 37 possible sums they will be mapped to, by the Pigeonhole Principle there will be at least two subsets with the same sum.

End of proof.