2007 BMO Problems/Problem 3

Problem

(Serbia) Find all positive integers $n$ such that there exists a permutation $\sigma$ on the set $\{ 1, \ldots, n \}$ for which

$\sqrt{\sigma(1) + \sqrt{\sigma(2) + \sqrt{ \cdots + \sqrt{\sigma(n)}}}}$

is a rational number.

Note: A permutation of the set $\{ 1, 2, \ldots, n \}$ is a one-to-one function of this set to itself.

Solution

The only solutions are $n=1$ and $n=3$ .

First, we will prove that for positive integers $a_1, \ldots, a_m$ , the number $\sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}}$ is rational if and only if $\sqrt{a_i + \sqrt{ + \cdots + \sqrt{a_1}}}$ is an integer, for all integers $1 \le i \le m$ . This follows from induction on $m$ . The case $m=1$ is trivial; now, suppose it holds for $a_1, \ldots, a_{m-1}$ . Then if $\sqrt{a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}}$ is an rational, than its square, $a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}$ must also be rational, which implies that $\sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}$ is rational. But by the inductive hypothesis, $\sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}$ must be an integer, so $a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}$ must also be an integer, which means that $\sqrt{a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}}$ is also an integer, since it is rational. The result follows.

Next, we prove that if $a_1, \ldots, a_m, k$ are positive integers such that $a_1, \ldots, a_m \le k^2$ and $\sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}}$ is rational, then $\sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}} \le k$ .

This also comes by induction. The case $m=1$ is trivial. If our result holds for any $a_1, \ldots, a_{m-1}$ , then

$\sqrt{a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}} \le \sqrt{k^2 + k}$ .

Since $a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} \le k^2 + k < (k+1)^2$ must be a perfect square, it can be at most $k^2$ , and the result follows.

Now we prove that no $n \ge 5$ is a solution.

Suppose that there is some $n \ge 5$ that is a solution. Than there exists some number $m^2+1 \le n$ such that $n \le (m+1)^2$ . Since $n \ge 5$ , $m \ge 2$ . If $m^2+1 =\sigma(i)$ , then we know $i \neq n$ since $m^2 + 1$ is not a square; and $\sigma(i) + \sqrt{\sigma(i+1) + \sqrt{ \cdots + \sqrt{\sigma(n)}}}$ must be a perfect square, so we must have $\sqrt{ \sigma(i+1) + \sqrt{ \cdots + \sqrt{ \sigma(n)}}} \ge 2m > m+1$ . But this is a contradiction.

We now have the cases $n=1,2,3,4$ to consider. The case $n=1$ is trivial. For $n=2$ it is easy to verify that neither $\sqrt{2 + \sqrt{1}}$ nor $\sqrt{1 + \sqrt{2}}$ is rational. For $n=3$ , we have the solution $\sqrt{ 2 + \sqrt{ 3 + \sqrt{1}}} = 2$ . We now consider. $n=4$ . First, suppose $4 \neq \sigma(4)$ ; say $\sigma(i) = 4$ . We have already shown that $x= \sqrt{ \sigma(i+1) + \sqrt{ \cdots + \sqrt{\sigma(4)}}} \le 2 < 5$ ; this means $4 < \sigma(i)+x <9$ , a contradiction, since $\sigma(i) + x$ must be a perfect square. Thus $\sigma(4) =4$ . But here we have either $\sqrt{1 + \sqrt{4}}$ is irrational, $\sqrt{3 + \sqrt{4}}$ is irrational, $\sqrt{1 + \sqrt{2 + \sqrt{4}}}$ is irrational, or $\sqrt{3 + \sqrt{2 + \sqrt{4}}}$ is irrational. Thus there is no solution for $n=4$ and the only solutions are $n=1, 3$ .