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 , 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.
--03:19, 16 August 2011 (EDT)