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
m (→‎Solution)
 
Line 28: Line 28:
 
Now we prove that no <math>n \ge 5 </math> is a solution.
 
Now we prove that no <math>n \ge 5 </math> is a solution.
  
−
Suppose that there is some <math> n \ge 5 </math> that is a solution.  Than there exists some number <math> m^2+1 \le n </math> such that <math> n \le (m+1)^2 </math>.  Since <math>n \ge 5 </math>, <math> m \ge 2 </math>.  If <math>\sigma (m^2+1) = i </math>, then we know <math>i \neq n </math>, since <math>m^2 + 1 </math> is not a square, and <math> \sigma(i) + \sqrt{\sigma(i+1) + \sqrt{ \cdots + \sqrt{\sigma(n)}}} </math> must be a perfect square, so we must have <math> \sqrt{ \sigma(i+1) + \sqrt{ \cdots + \sqrt{ \sigma(n)}}} \ge 2m > m+1 </math>.  But this is a contradiction.
+
Suppose that there is some <math> n \ge 5 </math> that is a solution.  Than there exists some number <math> m^2+1 \le n </math> such that <math> n \le (m+1)^2 </math>.  Since <math>n \ge 5 </math>, <math> m \ge 2 </math>.  If <math>m^2+1 =\sigma(i) </math>, then we know <math>i \neq n </math> since <math>m^2 + 1 </math> is not a square; and <math> \sigma(i) + \sqrt{\sigma(i+1) + \sqrt{ \cdots + \sqrt{\sigma(n)}}} </math> must be a perfect square, so we must have <math> \sqrt{ \sigma(i+1) + \sqrt{ \cdots + \sqrt{ \sigma(n)}}} \ge 2m > m+1 </math>.  But this is a contradiction.
  
 
We now have the cases <math>n=1,2,3,4 </math> to consider.  The case <math>n=1 </math> is trivial.  For <math>n=2 </math> it is easy to verify that neither <math> \sqrt{2 + \sqrt{1}} </math> nor <math> \sqrt{1 + \sqrt{2}} </math> is rational.  For <math>n=3 </math>, we have the solution <math> \sqrt{ 2 + \sqrt{ 3 + \sqrt{1}}} = 2 </math>.  We now consider. <math>n=4 </math>.  First, suppose <math>4 \neq \sigma(4) </math>; say <math>\sigma(i) = 4 </math>.  We have already shown that <math> x= \sqrt{ \sigma(i+1) + \sqrt{ \cdots + \sqrt{\sigma(4)}}} \le 2 < 5 </math>; this means <math>4 < \sigma(i)+x <9 </math>, a contradiction, since <math>\sigma(i) + x </math> must be a perfect square.  Thus <math>\sigma(4) =4 </math>.  But here we have either <math> \sqrt{1 + \sqrt{4}} </math> is irrational, <math> \sqrt{3 + \sqrt{4}} </math> is irrational, <math> \sqrt{1 + \sqrt{2 + \sqrt{4}}} </math> is irrational, or <math> \sqrt{3 + \sqrt{2 + \sqrt{4}}} </math> is irrational.  Thus there is no solution for <math>n=4 </math> and the only solutions are <math>n=1, 3 </math>.
 
We now have the cases <math>n=1,2,3,4 </math> to consider.  The case <math>n=1 </math> is trivial.  For <math>n=2 </math> it is easy to verify that neither <math> \sqrt{2 + \sqrt{1}} </math> nor <math> \sqrt{1 + \sqrt{2}} </math> is rational.  For <math>n=3 </math>, we have the solution <math> \sqrt{ 2 + \sqrt{ 3 + \sqrt{1}}} = 2 </math>.  We now consider. <math>n=4 </math>.  First, suppose <math>4 \neq \sigma(4) </math>; say <math>\sigma(i) = 4 </math>.  We have already shown that <math> x= \sqrt{ \sigma(i+1) + \sqrt{ \cdots + \sqrt{\sigma(4)}}} \le 2 < 5 </math>; this means <math>4 < \sigma(i)+x <9 </math>, a contradiction, since <math>\sigma(i) + x </math> must be a perfect square.  Thus <math>\sigma(4) =4 </math>.  But here we have either <math> \sqrt{1 + \sqrt{4}} </math> is irrational, <math> \sqrt{3 + \sqrt{4}} </math> is irrational, <math> \sqrt{1 + \sqrt{2 + \sqrt{4}}} </math> is irrational, or <math> \sqrt{3 + \sqrt{2 + \sqrt{4}}} </math> is irrational.  Thus there is no solution for <math>n=4 </math> and the only solutions are <math>n=1, 3 </math>.

Latest revision as of 10:53, 13 January 2016

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

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=74512"