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 (→‎Solution)
(Added Solution 2)
Line 11: Line 11:
 
'''''Note''': A permutation of the set <math> \{ 1, 2, \ldots, n \} </math> is a one-to-one function of this set to itself.''
 
'''''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 1 ==
 
The only solutions are <math>n=1 </math> and <math>n=3 </math>.
 
The only solutions are <math>n=1 </math> and <math>n=3 </math>.
  
Line 31: Line 31:
  
 
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>.
 +
 +
 +
== Solution 2 ==
 +
 +
We claim that the only positive integers satisfying the given condition are <math>n=1</math> and <math>n=3.</math> These indeed work since <math>\sqrt{1}=1</math> and
 +
<cmath>\sqrt{2+\sqrt{3+\sqrt{1}}}=\sqrt{2+\sqrt{4}}=2</cmath>are both rational.
 +
 +
First, we introduce some simplifying notation: Let <math>b_1,\ b_2,\ \ldots,\ b_m</math> be arbitrary positive integers. Then define
 +
<cmath>B_i=\sqrt{b_i + \sqrt{ b_{i-1} + \sqrt{\cdots + \sqrt{b_2+\sqrt{b_1}}}}}</cmath>for all <math>1 \le i \le m.</math>
 +
 +
We start by showing three lemmas:
 +
 +
Lemma 1: Let <math>k</math> be a positive integer. Then <math>\sqrt{k}</math> is rational if and only if <math>\sqrt{k}</math> is an integer.
 +
 +
Proof: First, note that if <math>\sqrt{k}</math> is an integer, it must be rational. Now, suppose <math>\sqrt{k}</math> is rational; then we can write <math>k=\dfrac{x^2}{y^2}</math> for some relatively prime positive integers <math>x</math> and <math>y.</math> Hence, <math>k \cdot y^2=x^2,</math> so <math>y^2 \mid x^2.</math> Since <math>x</math> and <math>y</math> are relatively prime, it follows that <math>y \mid x,</math> which can only happen if <math>y=1.</math> Hence, we have <math>k=x^2,</math> which means that <math>\sqrt{k}</math> is an integer. <math>\blacksquare</math>
 +
 +
Lemma 2: Let <math>b_1,\ b_2,\ \ldots,\ b_m</math> be arbitrary positive integers. Then <math>B_m</math> is rational if and only if <math>B_i</math> is an integer for all integers <math>1 \le i \le m.</math>
 +
 +
Proof: We prove this by induction on <math>m.</math> The base case <math>m=1</math> is given by Lemma 1. Now, suppose the statement is true for <math>m-1.</math> If <math>B_i</math> is an integer for all <math>1 \le i \le m,</math> then <math>B_m</math> is an integer, so <math>B_m</math> is rational.
 +
 +
Now, if <math>B_m</math> is rational, then <math>B_m^2-b_m=B_{m-1}</math> is also rational. By the inductive hypothesis, this is true if and only if <math>B_i</math> is an integer for all <math>1 \le i \le m-1.</math> In particular, <math>B_{m-1}</math> must be an integer, so <math>b_m+B_{m-1}</math> must also be an integer. Then, since <math>B_m</math> is rational by hypothesis, Lemma 1 tells us that <math>B_m=\sqrt{b_m+B_{m-1}}</math> must be an integer. Since we also know <math>B_i</math> is an integer for all <math>1 \le i \le m-1,</math> it follows that <math>B_i</math> is an integer for all <math>1 \le i \le m.</math> Hence, by induction, our statement is true for all <math>m,</math> as desired. <math>\blacksquare</math>
 +
 +
Lemma 3: Suppose that <math>b_1,\ b_2,\ \ldots,\ b_m,\ k</math> are positive integers such that <math>b_1,\ b_2,\ \ldots,\ b_m \le k^2,</math> and <math>B_m</math> is rational. Then we have <math>B_m \le k.</math>
 +
 +
Proof: Again, we prove this by induction on <math>m.</math> For the base case <math>m=1,</math> we know that since <math>b_1 \le k^2,</math> it follows that <math>\sqrt{b_1} \le k.</math>
 +
 +
Now, suppose the statement is true for <math>m-1,</math> and suppose <math>b_1,\ b_2,\ \ldots,\ b_m,\ k</math> are positive integers such that <math>b_1,\ b_2,\ \ldots,\ b_m \le k^2</math> and <math>B_m</math> is rational. Then we know that <math>B_{m-1}=B_m^2-b_m</math> is also rational, so by the inductive hypothesis, we have <math>B_{m-1} \le k.</math> Adding <math>b_m</math> and then taking the square root of both sides, it follows that
 +
<cmath>B_m = \sqrt{b_m+B_{m-1}} \le \sqrt{k+b_m} \le \sqrt{k^2+k},</cmath>where the last inequality comes from the fact that <math>b_m \le k^2.</math> However, since Lemma 2 tells us that <math>B_m</math> must be an integer and <math>k < \sqrt{k^2+k} < k+1,</math> it follows that we actually have <math>B_m \le \sqrt{k^2}=k.</math> Hence, by induction, our statement is true for all <math>m,</math> as desired. <math>\blacksquare</math>
 +
 +
Using these lemmas, we turn our attention to which positive integers <math>n</math> can satisfy the condition given in the problem. Similarly to our definition of <math>B_m</math> above, for a permutation <math>a_1,\ a_2,\ \ldots,\ a_n</math> of the numbers <math>1,\ 2,\ \ldots,\ n,</math> define
 +
<cmath>A_i=\sqrt{a_i + \sqrt{ a_{i-1} + \sqrt{\cdots + \sqrt{a_2+\sqrt{a_1}}}}}</cmath>for all <math>1 \le i \le n.</math>
 +
 +
First, we claim that no <math>n \ge 5</math> satisfies the given condition. Suppose for the sake of contradiction that some <math>n \ge 5</math> did satisfy the condition. Then there must exist some integer <math>m \ge 2</math> such that <math>m^2+1 \le n \le (m+1)^2,</math> so there must be some <math>1 \le i \le n</math> such that <math>a_i=m^2+1.</math> If <math>i=1,</math> we know from Lemma 2 that <math>A_1=\sqrt{a_1}</math> is an integer, a contradiction. Hence, <math>i \neq 1.</math> Then, Lemma 3 tells us that since <math>a_i,\ a_{i-1},\ \ldots,\ a_1</math> are at most <math>n</math> and hence less than <math>(m+1)^2,</math> we have <math>A_i \le m+1.</math> This means that
 +
<cmath>A_i^2 = a_i + A_{i-1} = (m^2+1)+A_{i-1} \le (m+1)^2.</cmath>Furthermore, since Lemma 2 tells us <math>A_i</math> is an integer, <math>A_i^2</math> must be a perfect square. Since <math>m^2<A_i^2 \le (m+1)^2,</math> it follows that <math>A_i^2=(m+1)^2,</math> so <math>A_{i-1}=2m.</math> Then, as Lemma 3 tells us that <math>A_{i-1} \le m+1,</math> this means that <math>2m \le m+1</math> and hence <math>m \le 1,</math> contradicting the fact that <math>m \ge 2.</math> Therefore, no <math>n \ge 5</math> satisfies the given conditions.
 +
 +
Hence, the only possible positive integers <math>n</math> that could satisfy the given condition are <math>n=1,\ 2,\ 3,</math> and <math>4.</math> We showed above that <math>n=1</math> and <math>n=3</math> do indeed satisfy the given condition, so it suffices to show that <math>n=2</math> and <math>n=4</math> do not. For <math>n=2,</math> we can verify using Lemma 1 that neither <math>\sqrt{1+\sqrt{2}}</math> nor <math>\sqrt{2+\sqrt{1}}</math> are rational, so this does not satisfy the given conditions.
 +
 +
Now, suppose <math>n=4</math> satisfies the given conditions. First, suppose for the sake of contradiction that <math>a_1 \neq 4</math> and that <math>a_i=4</math> for some <math>2 \le i \le 4.</math> Then Lemma 3 tells us that <math>A_{i-1} \le 2,</math> so <math>A_i^2=a_i+A_{i-1}</math> must both be a perfect square and equal to either <math>5</math> or <math>6,</math> which is a contradiction. Hence, we must have <math>a_1=4.</math> By Lemma 2, it then follows that one of the numbers
 +
<cmath>\sqrt{1+\sqrt{4}},\ \sqrt{3+\sqrt{4}},\ \sqrt{1+\sqrt{2+\sqrt{4}}},\ \sqrt{3+\sqrt{2+\sqrt{4}}}</cmath>is an integer. However, we can verify using Lemma 1 that none of these are integers, so <math>n=4</math> does not satisfy the given conditions.
 +
 +
This means that the only positive integers satisfying the given condition are <math>n=\boxed{1\text{ and }3},</math> as desired.
  
 
{{alternate solutions}}
 
{{alternate solutions}}

Revision as of 20:26, 15 September 2024

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 1

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


Solution 2

We claim that the only positive integers satisfying the given condition are $n=1$ and $n=3.$ These indeed work since $\sqrt{1}=1$ and \[\sqrt{2+\sqrt{3+\sqrt{1}}}=\sqrt{2+\sqrt{4}}=2\]are both rational.

First, we introduce some simplifying notation: Let $b_1,\ b_2,\ \ldots,\ b_m$ be arbitrary positive integers. Then define \[B_i=\sqrt{b_i + \sqrt{ b_{i-1} + \sqrt{\cdots + \sqrt{b_2+\sqrt{b_1}}}}}\]for all $1 \le i \le m.$

We start by showing three lemmas:

Lemma 1: Let $k$ be a positive integer. Then $\sqrt{k}$ is rational if and only if $\sqrt{k}$ is an integer.

Proof: First, note that if $\sqrt{k}$ is an integer, it must be rational. Now, suppose $\sqrt{k}$ is rational; then we can write $k=\dfrac{x^2}{y^2}$ for some relatively prime positive integers $x$ and $y.$ Hence, $k \cdot y^2=x^2,$ so $y^2 \mid x^2.$ Since $x$ and $y$ are relatively prime, it follows that $y \mid x,$ which can only happen if $y=1.$ Hence, we have $k=x^2,$ which means that $\sqrt{k}$ is an integer. $\blacksquare$

Lemma 2: Let $b_1,\ b_2,\ \ldots,\ b_m$ be arbitrary positive integers. Then $B_m$ is rational if and only if $B_i$ is an integer for all integers $1 \le i \le m.$

Proof: We prove this by induction on $m.$ The base case $m=1$ is given by Lemma 1. Now, suppose the statement is true for $m-1.$ If $B_i$ is an integer for all $1 \le i \le m,$ then $B_m$ is an integer, so $B_m$ is rational.

Now, if $B_m$ is rational, then $B_m^2-b_m=B_{m-1}$ is also rational. By the inductive hypothesis, this is true if and only if $B_i$ is an integer for all $1 \le i \le m-1.$ In particular, $B_{m-1}$ must be an integer, so $b_m+B_{m-1}$ must also be an integer. Then, since $B_m$ is rational by hypothesis, Lemma 1 tells us that $B_m=\sqrt{b_m+B_{m-1}}$ must be an integer. Since we also know $B_i$ is an integer for all $1 \le i \le m-1,$ it follows that $B_i$ is an integer for all $1 \le i \le m.$ Hence, by induction, our statement is true for all $m,$ as desired. $\blacksquare$

Lemma 3: Suppose that $b_1,\ b_2,\ \ldots,\ b_m,\ k$ are positive integers such that $b_1,\ b_2,\ \ldots,\ b_m \le k^2,$ and $B_m$ is rational. Then we have $B_m \le k.$

Proof: Again, we prove this by induction on $m.$ For the base case $m=1,$ we know that since $b_1 \le k^2,$ it follows that $\sqrt{b_1} \le k.$

Now, suppose the statement is true for $m-1,$ and suppose $b_1,\ b_2,\ \ldots,\ b_m,\ k$ are positive integers such that $b_1,\ b_2,\ \ldots,\ b_m \le k^2$ and $B_m$ is rational. Then we know that $B_{m-1}=B_m^2-b_m$ is also rational, so by the inductive hypothesis, we have $B_{m-1} \le k.$ Adding $b_m$ and then taking the square root of both sides, it follows that \[B_m = \sqrt{b_m+B_{m-1}} \le \sqrt{k+b_m} \le \sqrt{k^2+k},\]where the last inequality comes from the fact that $b_m \le k^2.$ However, since Lemma 2 tells us that $B_m$ must be an integer and $k < \sqrt{k^2+k} < k+1,$ it follows that we actually have $B_m \le \sqrt{k^2}=k.$ Hence, by induction, our statement is true for all $m,$ as desired. $\blacksquare$

Using these lemmas, we turn our attention to which positive integers $n$ can satisfy the condition given in the problem. Similarly to our definition of $B_m$ above, for a permutation $a_1,\ a_2,\ \ldots,\ a_n$ of the numbers $1,\ 2,\ \ldots,\ n,$ define \[A_i=\sqrt{a_i + \sqrt{ a_{i-1} + \sqrt{\cdots + \sqrt{a_2+\sqrt{a_1}}}}}\]for all $1 \le i \le n.$

First, we claim that no $n \ge 5$ satisfies the given condition. Suppose for the sake of contradiction that some $n \ge 5$ did satisfy the condition. Then there must exist some integer $m \ge 2$ such that $m^2+1 \le n \le (m+1)^2,$ so there must be some $1 \le i \le n$ such that $a_i=m^2+1.$ If $i=1,$ we know from Lemma 2 that $A_1=\sqrt{a_1}$ is an integer, a contradiction. Hence, $i \neq 1.$ Then, Lemma 3 tells us that since $a_i,\ a_{i-1},\ \ldots,\ a_1$ are at most $n$ and hence less than $(m+1)^2,$ we have $A_i \le m+1.$ This means that \[A_i^2 = a_i + A_{i-1} = (m^2+1)+A_{i-1} \le (m+1)^2.\]Furthermore, since Lemma 2 tells us $A_i$ is an integer, $A_i^2$ must be a perfect square. Since $m^2<A_i^2 \le (m+1)^2,$ it follows that $A_i^2=(m+1)^2,$ so $A_{i-1}=2m.$ Then, as Lemma 3 tells us that $A_{i-1} \le m+1,$ this means that $2m \le m+1$ and hence $m \le 1,$ contradicting the fact that $m \ge 2.$ Therefore, no $n \ge 5$ satisfies the given conditions.

Hence, the only possible positive integers $n$ that could satisfy the given condition are $n=1,\ 2,\ 3,$ and $4.$ We showed above that $n=1$ and $n=3$ do indeed satisfy the given condition, so it suffices to show that $n=2$ and $n=4$ do not. For $n=2,$ we can verify using Lemma 1 that neither $\sqrt{1+\sqrt{2}}$ nor $\sqrt{2+\sqrt{1}}$ are rational, so this does not satisfy the given conditions.

Now, suppose $n=4$ satisfies the given conditions. First, suppose for the sake of contradiction that $a_1 \neq 4$ and that $a_i=4$ for some $2 \le i \le 4.$ Then Lemma 3 tells us that $A_{i-1} \le 2,$ so $A_i^2=a_i+A_{i-1}$ must both be a perfect square and equal to either $5$ or $6,$ which is a contradiction. Hence, we must have $a_1=4.$ By Lemma 2, it then follows that one of the numbers \[\sqrt{1+\sqrt{4}},\ \sqrt{3+\sqrt{4}},\ \sqrt{1+\sqrt{2+\sqrt{4}}},\ \sqrt{3+\sqrt{2+\sqrt{4}}}\]is an integer. However, we can verify using Lemma 1 that none of these are integers, so $n=4$ does not satisfy the given conditions.

This means that the only positive integers satisfying the given condition are $n=\boxed{1\text{ and }3},$ as desired.

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