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 1

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$ .

Solution 2

We claim that the only positive integers satisfying the given condition are $n=1$ and $n=3.$ These indeed work since $\sqrt{1}=1$ and $\sqrt{2+\sqrt{3+\sqrt{1}}}=\sqrt{2+\sqrt{4}}=2$ are both rational.

First, we introduce some simplifying notation: Let $b_1,\ b_2,\ \ldots,\ b_m$ be arbitrary positive integers. Then define $B_i=\sqrt{b_i + \sqrt{ b_{i-1} + \sqrt{\cdots + \sqrt{b_2+\sqrt{b_1}}}}}$ for all $1 \le i \le m.$

We start by showing three lemmas:

Lemma 1: Let $k$ be a positive integer. Then $\sqrt{k}$ is rational if and only if $\sqrt{k}$ is an integer.

Proof: First, note that if $\sqrt{k}$ is an integer, it must be rational. Now, suppose $\sqrt{k}$ is rational; then we can write $k=\dfrac{x^2}{y^2}$ for some relatively prime positive integers $x$ and $y.$ Hence, $k \cdot y^2=x^2,$ so $y^2 \mid x^2.$ Since $x$ and $y$ are relatively prime, it follows that $y \mid x,$ which can only happen if $y=1.$ Hence, we have $k=x^2,$ which means that $\sqrt{k}$ is an integer. $\blacksquare$

Lemma 2: Let $b_1,\ b_2,\ \ldots,\ b_m$ be arbitrary positive integers. Then $B_m$ is rational if and only if $B_i$ is an integer for all integers $1 \le i \le m.$

Proof: We prove this by induction on $m.$ The base case $m=1$ is given by Lemma 1. Now, suppose the statement is true for $m-1.$ If $B_i$ is an integer for all $1 \le i \le m,$ then $B_m$ is an integer, so $B_m$ is rational.

Now, if $B_m$ is rational, then $B_m^2-b_m=B_{m-1}$ is also rational. By the inductive hypothesis, this is true if and only if $B_i$ is an integer for all $1 \le i \le m-1.$ In particular, $B_{m-1}$ must be an integer, so $b_m+B_{m-1}$ must also be an integer. Then, since $B_m$ is rational by hypothesis, Lemma 1 tells us that $B_m=\sqrt{b_m+B_{m-1}}$ must be an integer. Since we also know $B_i$ is an integer for all $1 \le i \le m-1,$ it follows that $B_i$ is an integer for all $1 \le i \le m.$ Hence, by induction, our statement is true for all $m,$ as desired. $\blacksquare$

Lemma 3: Suppose that $b_1,\ b_2,\ \ldots,\ b_m,\ k$ are positive integers such that $b_1,\ b_2,\ \ldots,\ b_m \le k^2,$ and $B_m$ is rational. Then we have $B_m \le k.$

Proof: Again, we prove this by induction on $m.$ For the base case $m=1,$ we know that since $b_1 \le k^2,$ it follows that $\sqrt{b_1} \le k.$

Now, suppose the statement is true for $m-1,$ and suppose $b_1,\ b_2,\ \ldots,\ b_m,\ k$ are positive integers such that $b_1,\ b_2,\ \ldots,\ b_m \le k^2$ and $B_m$ is rational. Then we know that $B_{m-1}=B_m^2-b_m$ is also rational, so by the inductive hypothesis, we have $B_{m-1} \le k.$ Adding $b_m$ and then taking the square root of both sides, it follows that $B_m = \sqrt{b_m+B_{m-1}} \le \sqrt{k+b_m} \le \sqrt{k^2+k},$ where the last inequality comes from the fact that $b_m \le k^2.$ However, since Lemma 2 tells us that $B_m$ must be an integer and $k < \sqrt{k^2+k} < k+1,$ it follows that we actually have $B_m \le \sqrt{k^2}=k.$ Hence, by induction, our statement is true for all $m,$ as desired. $\blacksquare$

Using these lemmas, we turn our attention to which positive integers $n$ can satisfy the condition given in the problem. Similarly to our definition of $B_m$ above, for a permutation $a_1,\ a_2,\ \ldots,\ a_n$ of the numbers $1,\ 2,\ \ldots,\ n,$ define $A_i=\sqrt{a_i + \sqrt{ a_{i-1} + \sqrt{\cdots + \sqrt{a_2+\sqrt{a_1}}}}}$ for all $1 \le i \le n.$

First, we claim that no $n \ge 5$ satisfies the given condition. Suppose for the sake of contradiction that some $n \ge 5$ did satisfy the condition. Then there must exist some integer $m \ge 2$ such that $m^2+1 \le n \le (m+1)^2,$ so there must be some $1 \le i \le n$ such that $a_i=m^2+1.$ If $i=1,$ we know from Lemma 2 that $A_1=\sqrt{a_1}$ is an integer, a contradiction. Hence, $i \neq 1.$ Then, Lemma 3 tells us that since $a_i,\ a_{i-1},\ \ldots,\ a_1$ are at most $n$ and hence less than $(m+1)^2,$ we have $A_i \le m+1.$ This means that $A_i^2 = a_i + A_{i-1} = (m^2+1)+A_{i-1} \le (m+1)^2.$ Furthermore, since Lemma 2 tells us $A_i$ is an integer, $A_i^2$ must be a perfect square. Since $m^2<A_i^2 \le (m+1)^2,$ it follows that $A_i^2=(m+1)^2,$ so $A_{i-1}=2m.$ Then, as Lemma 3 tells us that $A_{i-1} \le m+1,$ this means that $2m \le m+1$ and hence $m \le 1,$ contradicting the fact that $m \ge 2.$ Therefore, no $n \ge 5$ satisfies the given conditions.

Hence, the only possible positive integers $n$ that could satisfy the given condition are $n=1,\ 2,\ 3,$ and $4.$ We showed above that $n=1$ and $n=3$ do indeed satisfy the given condition, so it suffices to show that $n=2$ and $n=4$ do not. For $n=2,$ we can verify using Lemma 1 that neither $\sqrt{1+\sqrt{2}}$ nor $\sqrt{2+\sqrt{1}}$ are rational, so this does not satisfy the given conditions.

Now, suppose $n=4$ satisfies the given conditions. First, suppose for the sake of contradiction that $a_1 \neq 4$ and that $a_i=4$ for some $2 \le i \le 4.$ Then Lemma 3 tells us that $A_{i-1} \le 2,$ so $A_i^2=a_i+A_{i-1}$ must both be a perfect square and equal to either $5$ or $6,$ which is a contradiction. Hence, we must have $a_1=4.$ By Lemma 2, it then follows that one of the numbers $\sqrt{1+\sqrt{4}},\ \sqrt{3+\sqrt{4}},\ \sqrt{1+\sqrt{2+\sqrt{4}}},\ \sqrt{3+\sqrt{2+\sqrt{4}}}$ is an integer. However, we can verify using Lemma 1 that none of these are integers, so $n=4$ does not satisfy the given conditions.