2001 IMO Shortlist Problems/N6

Problem

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

Solution

The answer is yes.

First Solution:

For example, let's say that the integers are, . Now this turns into a problem of solving for the  integers . This then each ai takes on the form, . Then we must find the   integers. By doing this process over and over again, we obtain the last  numbers, . Obviously these 3 integers can have different sums, and the number of different "parts" in every sequence (the number of terms that are different for , etc.) is , not exceeding .

Second Solution:

Lemma: We try to show that for a prime $p$ , there are such $p$ integers less than or equal to $2p^2$ . Then it suffices because $p=101>100$ and $2\cdot 101^2<25000$ is enough.

Proof: $\qquad$ Define $\bar a$ to be $a^2\equiv \bar a\bmod p$ and $\hat i=2pi+\bar i$ . Then, we show that the integers $\hat i$ does the trick for $i=1$ to $p$ . If $\hat a+\hat b\equiv \hat c+\hat d\pmod p$ , then $2(a+b)p+\bar a+\bar b\equiv 2(c+d)p+\bar c+\bar d\pmod p$ . Thus, we may say that $a+b\equiv c+d\pmod p\qquad (\dag)$ and, $\bar a+\bar b\equiv \bar c+\bar d\pmod p\qquad(*)$ since $\bar a<p$ . From $(\dag)$ , we have $a\equiv c+d-b\pmod p$ . From $(*)$ , we infer that $a^2+b^2\equiv c^2+d^2\pmod p$ which gives us $(c+d-b)^2+b^2\equiv c^2+d^2\pmod p$ . Factorizing, $2(b^2-bc-bd+cd)\equiv0\pmod p$ $\implies(b-c)(b-d)\equiv0\pmod p$