IMO 1983 SL 15

Origin: POL

Problem

Decide whether there exists a set M of natural numbers satis- fying the following conditions: (i) For any natural number m > 1 there are a, b \inM such that a+b = m. (ii) If a, b, c, d \inM, a, b, c, d > 10 and a + b = c + d, then a = c or a = d.

Solution

There is no such set. Suppose M satisfies (a) and (b) and let qn = |{a \inM : a \leqn}|. Consider the differences b −a, where a, b \inM and 10 < a < b \leqk. They are all positive and less than k, and (b) implies that they are
qk−q10  different integers. Hence
qk−q10  < k, so qk \leq \sqrt 2k +10. It follows from (a) that among the numbers of the form a + b, where a, b \inM, a \leqb \leqn, or a \leqn < b \leq2n, there are all integers from the interval [2, 2n + 1]. Thus
qn+1 

• qn(q2n −qn) \geq2n for every n \inN. Set Qk = \sqrt 2k + 10. We have

qn + 1 

• qn(q2n −qn) = 1 2qn + 1 2qn(2q2n −qn) \leq1 2qn + 1 2qn(2Q2n −qn) \leq1 2Qn + 1 2Qn(2Q2n −Qn) \leq2( \sqrt 2 −1)n + (20 + \sqrt 2/2)\sqrtn + 55, which is less than n for n large enough, a contradiction.