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)
m (→‎Solution)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
−
 
 
(''Serbia'')
 
(''Serbia'')
−
Find all positive integers <math> \displaystyle n </math> such that there exists a permutation <math> \displaystyle \sigma </math> on the set <math> \{ 1, \ldots, n \} </math> for which
+
Find all positive integers <math>n </math> such that there exists a permutation <math>\sigma </math> on the set <math> \{ 1, \ldots, n \} </math> for which
 
<center>
 
<center>
 
<math>
 
<math>
Line 13: Line 12:
  
 
== Solution ==
 
== Solution ==
 +
The only solutions are <math>n=1 </math> and <math>n=3 </math>.
  
−
The only solutions are <math> \displaystyle n=1 </math> and <math> \displaystyle n=3 </math>.
+
First, we will prove that for positive integers <math> a_1, \ldots, a_m </math>, the number <math> \sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}} </math> is rational if and only if <math> \sqrt{a_i + \sqrt{ + \cdots  + \sqrt{a_1}}} </math> is an integer, for all integers <math> 1 \le i \le m </math>.  This follows from induction on <math>m </math>.  The case <math>m=1 </math> is trivial; now, suppose it holds for <math> a_1, \ldots, a_{m-1} </math>.  Then if <math> \sqrt{a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}} </math> is an rational, than its square, <math> a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} </math> must also be rational, which implies that <math> \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} </math> is rational.  But by the inductive hypothesis, <math> \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} </math> must be an integer, so <math> a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} </math> must also be an integer, which means that <math> \sqrt{a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}} </math> is also an integer, since it is rational.  The result follows.
−
 
 
−
First, we will prove that for positive integers <math> a_1, \ldots, a_m </math>, the number <math> \sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}} </math> is rational if and only if <math> \sqrt{a_i + \sqrt{ + \cdots  + \sqrt{a_1}}} </math> is an integer, for all integers <math> 1 \le i \le m </math>.  This follows from induction on <math> \displaystyle m </math>.  The case <math> \displaystyle m=1 </math> is trivial; now, suppose it holds for <math> a_1, \ldots, a_{m-1} </math>.  Then if <math> \sqrt{a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}} </math> is an rational, than its square, <math> a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} </math> must also be rational, which implies that <math> \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} </math> is rational.  But by the inductive hypothesis, <math> \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} </math> must be an integer, so <math> a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} </math> must also be an integer, which means that <math> \sqrt{a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}}} </math> is also an integer, since it is rational.  The result follows.
 
  
 
Next, we prove that if <math> a_1, \ldots, a_m, k </math> are positive integers such that <math> a_1, \ldots, a_m \le k^2 </math> and <math> \sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}} </math> is rational, then <math> \sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}} \le k </math>.
 
Next, we prove that if <math> a_1, \ldots, a_m, k </math> are positive integers such that <math> a_1, \ldots, a_m \le k^2 </math> and <math> \sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}} </math> is rational, then <math> \sqrt{a_m + \sqrt{ \cdots + \sqrt{a_1}}} \le k </math>.
  
−
This also comes by induction.  The case <math> \displaystyle m=1 </math> is trivial.  If our result holds for any <math> a_1, \ldots, a_{m-1} </math>, then
+
This also comes by induction.  The case <math>m=1 </math> is trivial.  If our result holds for any <math> a_1, \ldots, a_{m-1} </math>, then
 
<center>
 
<center>
 
<math>
 
<math>
Line 26: Line 24:
 
</math>.
 
</math>.
 
</center>
 
</center>
−
Since <math> \displaystyle a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} \le k^2 + k < (k+1)^2 </math> must be a perfect square, it can be at most <math> \displaystyle k^2 </math>, and the result follows.
+
Since <math>a_m + \sqrt{a_{m-1} + \sqrt{ \cdots + \sqrt{a_1}}} \le k^2 + k < (k+1)^2 </math> must be a perfect square, it can be at most <math>k^2 </math>, and the result follows.
  
−
Now we prove that no <math> \displaystyle 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> \displaystyle n \ge 5 </math>, <math> m \ge 2 </math>.  If <math> \displaystyle \sigma (m^2+1) = i </math>, then we know <math> \displaystyle i \neq n </math>, since <math> \displaystyle 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> \displaystyle n=1,2,3,4 </math> to consider.  The case <math> \displaystyle n=1 </math> is trivial.  For <math> \displaystyle 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> \displaystyle n=3 </math>, we have the solution <math> \sqrt{ 2 + \sqrt{ 3 + \sqrt{1}}} = 2 </math>.  We now consider. <math> \displaystyle n=4 </math>.  First, suppose <math> \displaystyle 4 \neq \sigma(4) </math>; say <math> \displaystyle \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> \displaystyle 4 < \sigma(i)+x <9 </math>, a contradiction, since <math> \displaystyle \sigma(i) + x </math> must be a perfect square.  Thus <math> \displaystyle \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> \displaystyle n=4 </math> and the only solutions are <math> \displaystyle 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>.
  
 
{{alternate solutions}}
 
{{alternate solutions}}
  
 
== Resources ==
 
== Resources ==
−
 
 
* [[2007 BMO Problems]]
 
* [[2007 BMO Problems]]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=827183#827183 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=827183#827183 Discussion on AoPS/MathLinks]
−
 
  
 
[[Category:Olympiad Number Theory Problems]]
 
[[Category:Olympiad Number Theory Problems]]

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"