Russian 2000 Problem 17 S is a finite set of numbers such that given any three there are two whose sum is in S. What is the largest number of elements that S can have?
7 Solution Consider S = {-3, -2, -1, 0, 1, 2, 3}. Suppose {a, b, c} ⊆ S. If a = 0, then a+b ∈ S. If a and b have opposite sign, then |a+b| < max(|a|,|b|), so a+b ∈ S. The only remaining possibilities are {1,2,3} and {-3,-2,-1} and 1+2, -1-2 ∈ S. So there is a set with 7 elements having the required property. Now suppose S has 4 positive elements. Take the largest four: a < b < c < d. Consider {b,c,d}. Clearly c+d, b+d ∉ S, so b+c ∈ S and hence b+c = d. But the same argument shows that a+c = d, so a = b. Contradiction. Hence S has at most 3 positive elements. Similarly, it has at most 3 negative elements, and hence at most 7 elements in all. Russian 2000 © John Scholes jscholes@kalva.demon.co.uk 20 December 2003