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

I like pie (talk | contribs) 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> | + | 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 09:53, 13 January 2016

## 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.*