Show that any subset of the set {1,2,3,...,18} of cardinality 10 or more must have two elements whose sum is 19. (Can't use brute force)

I understand what the question is asking but i don't know how to answer it without using brute force.

Question

Show that any subset of the set {1,2,3,...,18} of cardinality 10 or more must have two elements whose sum is 19. (Can't use brute force) 

I understand what the question is asking but i don't know how to answer it without using brute force.

anonymous · Answer

I'm thinking all the possible sums for 19 are {(18,1), (17,2), (16,3), (15,4), (14,5), (13,6), (12,7), (11,8), (10,9)} This set is of cardinality 9. meaning if the subset has cardinality 10 it must contain at least two of the numbers shown above. IDK if that makes sense, any thoughts?

anonymous · Answer

^ I don't think that makes sense...

ganeshie8 · Answer

can we use pigeonhole principle ?

dumbcow · Answer

well by very nature that size must be 10 or more then that forces a combination of odd/even numbers and at least 1 number greater than 9 
thus one of the combinations you listed must exist in all possible subsets

anonymous · Answer

Ganeshie8, I just checked my textbook index and it is in it so yes we can but I don't know it too well.