Let S = {1, 4, 7, 10, 13, 16, ... , 100}. Let T be a subset of 20 elements of S. Show that we can find two distinct elements of T with sum 104.
Solution
Easy
Not best possible: we can make do with 19 elements. Note that the numbers have the form 3n + 1 for n = 0, 1, ... , 33. We seek 3n + 1, 3m + 1 so that n + m = 34. Evidently n = 0 and n = 17 do not help. The other 32 numbers form 16 pairs with the required sum. So if we take 19 numbers then we are sure to get two from the same pair.
© John Scholes
jscholes@kalva.demon.co.uk
3 Nov 1999