2007 BMO Problems/Problem 3

Problem

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

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

is a rational number.

Solution

The only solutions are $\displaystyle n=1$ and $\displaystyle 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 $\displaystyle m$ . The case $\displaystyle 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 $\displaystyle 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 $\displaystyle 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 $\displaystyle k^2$ , and the result follows.

Now we prove that no $\displaystyle 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 $\displaystyle n \ge 5$ , $m \ge 2$ . If $\displaystyle \sigma (m^2+1) = i$ , then we know $\displaystyle i \neq n$ , since $\displaystyle 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 $\displaystyle n=1,2,3,4$ to consider. The case $\displaystyle n=1$ is trivial. For $\displaystyle n=2$ it is easy to verify that neither $\sqrt{2 + \sqrt{1}}$ nor $\sqrt{1 + \sqrt{2}}$ is rational. For $\displaystyle n=3$ , we have the solution $\sqrt{ 2 + \sqrt{ 3 + \sqrt{1}}} = 2$ . We now consider. $\displaystyle n=4$ . First, suppose $\displaystyle 4 \neq \sigma(4)$ ; say $\displaystyle \sigma(i) = 4$ . We have already shown that $x= \sqrt{ \sigma(i+1) + \sqrt{ \cdots + \sqrt{\sigma(4)}}} \le 2 < 5$ ; this means $\displaystyle 4 < \sigma(i)+x <9$ , a contradiction, since $\displaystyle \sigma(i) + x$ must be a perfect square. Thus $\displaystyle \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 $\displaystyle n=4$ and the only solutions are $\displaystyle n=1, 3$ .