Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2007 BMO Problems/Problem 3"

 
m (official wording)
Line 5: Line 5:
 
<center>
 
<center>
 
<math>
 
<math>
−
\sqrt{\sigma(1) + \sqrt{\sigma(2) + \sqrt{ \cdots + \sqrt{\sigma(n-1) + \sqrt{\sigma(n)}}}}}
+
\sqrt{\sigma(1) + \sqrt{\sigma(2) + \sqrt{ \cdots + \sqrt{\sigma(n)}}}}
 
</math>
 
</math>
 
</center>
 
</center>
 
is a rational number.
 
is a rational number.
 +
 +
'''''Note''': A permutation of the set <math> \{ 1, 2, \ldots, n \} </math> is a one-to-one function of this set to itself.''
  
 
== Solution ==
 
== Solution ==

Revision as of 22:48, 4 May 2007

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)}}}}$

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


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_BMO_Problems/Problem_3&oldid=14824"