2007 BMO Problems/Problem 3
(Serbia) Find all positive integers such that there exists a permutation on the set for which
is a rational number.
Note: A permutation of the set is a one-to-one function of this set to itself.
The only solutions are and .
First, we will prove that for positive integers , the number is rational if and only if is an integer, for all integers . This follows from induction on . The case is trivial; now, suppose it holds for . Then if is an rational, than its square, must also be rational, which implies that is rational. But by the inductive hypothesis, must be an integer, so must also be an integer, which means that is also an integer, since it is rational. The result follows.
Next, we prove that if are positive integers such that and is rational, then .
This also comes by induction. The case is trivial. If our result holds for any , then
Since must be a perfect square, it can be at most , and the result follows.
Now we prove that no is a solution.
Suppose that there is some that is a solution. Than there exists some number such that . Since , . If , then we know since is not a square; and must be a perfect square, so we must have . But this is a contradiction.
We now have the cases to consider. The case is trivial. For it is easy to verify that neither nor is rational. For , we have the solution . We now consider. . First, suppose ; say . We have already shown that ; this means , a contradiction, since must be a perfect square. Thus . But here we have either is irrational, is irrational, is irrational, or is irrational. Thus there is no solution for and the only solutions are .
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.