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

m (official wording) |
I like pie (talk | contribs) m |
||

Line 1: | Line 1: | ||

== Problem == | == Problem == | ||

− | |||

(''Serbia'') | (''Serbia'') | ||

− | Find all positive integers <math> | + | 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>. | ||

− | + | 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> | ||

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

− | |||

− | |||

+ | 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]] |

## Revision as of 02:32, 23 April 2008

## Problem

(*Serbia*)
Find all positive integers such that there exists a permutation on the set for which

is a rational number.

**Note**: A permutation of the set is a one-to-one function of this set to itself.

## Solution

The only solutions are and .

First, we will prove that for positive integers , the number is rational if and only if is an integer, for all integers . This follows from induction on . The case is trivial; now, suppose it holds for . Then if is an rational, than its square, must also be rational, which implies that is rational. But by the inductive hypothesis, must be an integer, so must also be an integer, which means that is also an integer, since it is rational. The result follows.

Next, we prove that if are positive integers such that and is rational, then .

This also comes by induction. The case is trivial. If our result holds for any , then

.

Since must be a perfect square, it can be at most , and the result follows.

Now we prove that no is a solution.

Suppose that there is some that is a solution. Than there exists some number such that . Since , . If , then we know , since is not a square, and must be a perfect square, so we must have . But this is a contradiction.

We now have the cases to consider. The case is trivial. For it is easy to verify that neither nor is rational. For , we have the solution . We now consider. . First, suppose ; say . We have already shown that ; this means , a contradiction, since must be a perfect square. Thus . But here we have either is irrational, is irrational, is irrational, or is irrational. Thus there is no solution for and the only solutions are .

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