Prove that if S is a subset of {0,1,2,...,2n} containing more than n elements, then there must exist x,y,z in S such that x+y=z.
(This smells like an Olympiad problem to me. In fact, I may well have solved this very problem forty years ago, but I don't see how to solve it now. Some sort of pigeonhole argument, sure, but how to set it up?)
... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... This is problem 36 in Bela Bollobas's "The Art of Mathematics: Coffee Time in Memphis", which gives the following solution: ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... ... spoiler space ... (First, note that we may assume 0 isn't in S since 0+0=0; Bollobas's statement of the problem assumes that explicitly.) Let a = min(S) and let T = {s-a : s in S, s /= a}. S has more than n elements, T has n elements, so between them they have more than 2n, and all these elements have 1 <= x <= 2n. So they must have an element in common. That is, we have s = s'-a; which is to say, s' = s+a. Done. Note that this actually proves somewhat more than was asked for. -- g