2001 IMO Shortlist Problems/N6
Is it possible to find 100 positive integers not exceeding 25,000, such that all pairwise sums of them are different?
The answer is yes.
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 .
Lemma: We try to show that for a prime , there are such integers less than or equal to . Then it suffices because and is enough.
Proof: Define to be and . Then, we show that the integers does the trick for to . If , then . Thus, we may say that and, since . From , we have . From , we infer that which gives us . Factorizing,
This yields or . But , and this implies that . The other case is similar. So, we are done.
Therefore, every sum must be distinct, as desired.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.