### 39th Putnam 1978

**Problem A1**

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.

39th Putnam 1978

© John Scholes

jscholes@kalva.demon.co.uk

3 Nov 1999