Prove that for all integers , there exists distinct positive integers such that
Solutions — 2
Solution 1
We will construct such by induction on .
Base case: .
Let , , . Then
Inductive step:
Suppose for some , there exist distinct positive integers such that
We will construct such that are distinct positive integers and
Note that
By the induction hypothesis, the first sum is , so we want
which means
But this is not possible for positive integers. Instead, we modify the construction.
Let us try a different approach. Let , , , and for , define .
Let us check that this works. For , , , , .
Compute all pairwise products:
But let's add them up:
So the total is , which is not .
Therefore, the above construction does not work for .
Let us try another construction.
Let , where is the -th prime number. For , , , .
So this does not work either.
Let us try a general construction. Let , , , and for , . For , as above, which did not work.
Alternatively, let us try for .
For , , , :
For , , , , :
Again, not .
Let us try a general formula. Let , , , , and so on. The sum is
Let , then
So
We want this to be .
Let us try , , :
So
So for , it works.
For , , , , .
Let .
We want
So
Let us try :
So
Therefore, the construction is nontrivial. The original source for this problem is the 1995 IMO Shortlist, and the solution is as follows:
Let , , , and for , define .
We claim that for all , the set , , , , , , ... works.
Let us prove this by induction.
Base case: is already shown.
Inductive step: Suppose for , are as above and
Now, for , .
Consider
By induction, the first sum is . The second sum is
But , so is a sum of reciprocals of divisors of .
But for the construction, it can be shown by induction that
for , , , , , ...
Therefore,
So
But this is not unless is infinite.
Therefore, the construction is more subtle. The correct construction is as follows:
Let , , , and for , .
Then, for ,
This can be proved by induction, as shown in the official solution to the 1995 IMO Shortlist problem N6.
Therefore, for all , such exist.
Solution 2
Let us first introduce some notation: given positive integers and , will denote the th elementary symmetric polynomial in the -variables .
We define a sequence of sets inductively as follows: . Now for , suppose with . Then is defined to be the set
Now for , we will use induction to prove the following two statements:
(1) ; and
(2) .
Both of these statements are easy to verify for . Now for the induction step, suppose , so that for and . By definition, . Note that
Here we have used (2) for . This shows (1). Further, we have
This proves (2), and the induction is finished. The given condition is equivalent to (1), and thus we are done.