IMO 2001 SL N6

Origin: RUS | Category: Number Theory

Problem

Is it possible to find 100 positive integers not exceeding 25,000 such that all pairwise sums of them are different?

Solution

Yes. The desired result is an immediate consequence of the following fact applied on p = 101. Lemma. For any odd prime number p, there exist p nonnegative integers less than 2p2 with all pairwise sums mutually distinct. Proof. We claim that the numbers an = 2np + (n2) have the desired property, where (x) denotes the remainder of x upon division by p. Suppose that ak + al = am + an. By the construction of ai, we have 2p(k +l) \leqak +al < 2p(k +l +1). Hence we must have k +l = m+n, and therefore also (k2) + (l2) = (m2) + (n2). Thus k + l \equivm + n and k2 + l2 \equivm2 + n2 (mod p). But then it holds that (k −l)2 = 2(k2 +l2)−(k +l)2 \equiv(m−n)2 (mod p), so k −l \equiv\pm(m −n), which leads to (k, l) = (m, n). This proves the lemma.