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 "Mock AIME II 2012 Problems/Problem 2"

(Created page with "==Problem== Let <math>\{a_n\}</math> be a recursion defined such that <math>a_1=1, a_2=20</math>, and <math>a_n=\sqrt{\left| a_{n-1}^2-a_{n-2}^2 \right|}</math> where <math>n\ge ...")
 
(→‎Solution)
 
(4 intermediate revisions by 3 users not shown)
Line 9: Line 9:
 
The first perfect square less than <math>20^2</math> is <math>19^2=361</math>.  Therefore <math>k=\sqrt{361}=19</math>.  
 
The first perfect square less than <math>20^2</math> is <math>19^2=361</math>.  Therefore <math>k=\sqrt{361}=19</math>.  
  
−
We present two ways to finding <math>m</math>:
+
We present three ways to finding <math>m</math>:
−
'''Way 1:'''  Now notice that, for <math> n\equiv1(\bmod3) </math>, we have <math> a_n=1 </math>. Also, the terms under the radical counts down one for every <math> a_n </math> such that <math> a_n\not\equiv1(\bmod3 ) </math>. The number of <math> n\equiv1(\bmod 3) </math> before a number <math> n </math> can be seen to be <math> \lceil \frac{n}{3}\rceil </math>. Therefore, we can see that <math> a_n=\sqrt{401-n+\lceil\frac{n}{3}\rceil} </math>. Setting this equal to <math> 19 </math>, we see that''' <math> n-\lceil\frac{n}{3}\rceil=40 </math>. We can see that both <math> n=60 </math> and <math> n=61 </math> satisfy this, however, since <math> 61\equiv1(\bmod3) </math>, we disregard this, and we find that <math> a_{60}=19 </math>, so <math>m=60</math>.
+
 
 +
'''Way 1:'''  Now notice that, for <math> n\equiv1(\bmod3) </math>, we have <math> a_n=1 </math>. Also, the terms under the radical counts down one for every <math> a_n </math> such that <math> a_n\not\equiv1(\bmod3 ) </math>. The number of <math> n\equiv1(\bmod 3) </math> before a number <math> n </math> can be seen to be <math> \lceil \frac{n}{3}\rceil </math>. Therefore, we can see that <math> a_n=\sqrt{401-n+\lceil\frac{n}{3}\rceil} </math>. Setting this equal to <math> 19 </math>, we see that <math> n-\lceil\frac{n}{3}\rceil=40 </math>. We can see that both <math> n=60 </math> and <math> n=61 </math> satisfy this, however, since <math> 61\equiv1(\bmod3) </math>, we disregard this, and we find that <math> a_{60}=19 </math>, so <math>m=60</math>.
  
  
Line 16: Line 17:
 
<math>1, (20, \sqrt{399}, 1), (\sqrt{398}, \sqrt{397}, 1), (\sqrt{396}, \sqrt{395}, 1), \cdots (\sqrt{362}, \sqrt{361}, 1)</math>.  Note that the number of these groups of three that we have is equal to the number of terms in the sequence <math>(361, 363, 365, \cdots 399)</math>.  This has <math>\frac{399-359}{2}=20</math> terms in it.  Before the last group, we have <math>19*3+1=58</math> terms, and <math>\sqrt{361}</math> is therefore the <math>60</math>th term, and <math>m=60</math>.
 
<math>1, (20, \sqrt{399}, 1), (\sqrt{398}, \sqrt{397}, 1), (\sqrt{396}, \sqrt{395}, 1), \cdots (\sqrt{362}, \sqrt{361}, 1)</math>.  Note that the number of these groups of three that we have is equal to the number of terms in the sequence <math>(361, 363, 365, \cdots 399)</math>.  This has <math>\frac{399-359}{2}=20</math> terms in it.  Before the last group, we have <math>19*3+1=58</math> terms, and <math>\sqrt{361}</math> is therefore the <math>60</math>th term, and <math>m=60</math>.
  
−
Both ways lead to <math>m=60</math> and <math>k=19</math>, so the answer is <math> 60+19=\boxed{079} </math>.   
+
Both ways lead to <math>m=60</math> and <math>k=19</math>, so the answer is <math> 60+19=\boxed{79} </math>.   
  
 
To show that no smaller sums can be created, note that the next perfect square will be <math>k=18</math> and will take more than <math>60+(19^2-18^2)=97</math> as the value of <math>m</math>, and hence all other perfect squares will take more than <math>97</math>, and we have <math>97+k</math> as our sum which is greater than <math>79</math> since <math>k\ge 2</math>.
 
To show that no smaller sums can be created, note that the next perfect square will be <math>k=18</math> and will take more than <math>60+(19^2-18^2)=97</math> as the value of <math>m</math>, and hence all other perfect squares will take more than <math>97</math>, and we have <math>97+k</math> as our sum which is greater than <math>79</math> since <math>k\ge 2</math>.
 +
 +
'''Way 3'''
 +
 +
We must ignore the cases where <math>a_n=1</math>, as required by the problem statement. Write <math>a_n=\sqrt{400-k}</math> for some integers <math>k,a_n</math>. We want to minimize <math>a_n+n</math>. Note if <math>a_n</math> is even (<math>k</math> is even) then <math>n=1.5k+2</math>, and if <math>a_n</math> is odd (<math>k</math> is odd), then <math>n=1.5k+1.5</math>. Rewrite <math>k=400-a_n^2</math> and note that <math>a_n</math> is at most <math>19</math>. In the case that <math>a_n</math> is odd, we have <math>a_n+n=a_n+1.5(400-a_n^2)+1.5</math>. This is a quadratic in <math>a_n</math> and is strictly decreasing for <math>a_n>0</math>, so to minimize we should choose <math>a_n=19</math>, which gives <math>a_n+n=79</math>. Do the case for <math>a_n</math> even as well, you find that <math>79</math> is the lowest.

Latest revision as of 23:06, 5 October 2017

Problem

Let $\{a_n\}$ be a recursion defined such that $a_1=1, a_2=20$, and $a_n=\sqrt{\left| a_{n-1}^2-a_{n-2}^2 \right|}$ where $n\ge 3$, and $n$ is an integer. If $a_m=k$ for $k$ being a positive integer greater than $1$ and $m$ being a positive integer greater than 2, find the smallest possible value of $m+k$.

Solution

The sequence goes as follows: $1, 20, \sqrt{399}, 1, \sqrt{398}, \sqrt{397}, 1, \sqrt{396}, \sqrt{395}, 1, \cdots$ Note that this sequence repeats, because once we get to $1$, we subtract $1$ from the number under the square root sign and take the square root of that, then when you take the difference of the squares of these two numbers, they have a difference of $1$, so you get back to $1$.

The first perfect square less than $20^2$ is $19^2=361$. Therefore $k=\sqrt{361}=19$.

We present three ways to finding $m$:

Way 1: Now notice that, for $n\equiv1(\bmod3)$, we have $a_n=1$. Also, the terms under the radical counts down one for every $a_n$ such that $a_n\not\equiv1(\bmod3 )$. The number of $n\equiv1(\bmod 3)$ before a number $n$ can be seen to be $\lceil \frac{n}{3}\rceil$. Therefore, we can see that $a_n=\sqrt{401-n+\lceil\frac{n}{3}\rceil}$. Setting this equal to $19$, we see that $n-\lceil\frac{n}{3}\rceil=40$. We can see that both $n=60$ and $n=61$ satisfy this, however, since $61\equiv1(\bmod3)$, we disregard this, and we find that $a_{60}=19$, so $m=60$.


Way 2: Look at the sequence by grouping terms as follows: $1, (20, \sqrt{399}, 1), (\sqrt{398}, \sqrt{397}, 1), (\sqrt{396}, \sqrt{395}, 1), \cdots (\sqrt{362}, \sqrt{361}, 1)$. Note that the number of these groups of three that we have is equal to the number of terms in the sequence $(361, 363, 365, \cdots 399)$. This has $\frac{399-359}{2}=20$ terms in it. Before the last group, we have $19*3+1=58$ terms, and $\sqrt{361}$ is therefore the $60$th term, and $m=60$.

Both ways lead to $m=60$ and $k=19$, so the answer is $60+19=\boxed{79}$.

To show that no smaller sums can be created, note that the next perfect square will be $k=18$ and will take more than $60+(19^2-18^2)=97$ as the value of $m$, and hence all other perfect squares will take more than $97$, and we have $97+k$ as our sum which is greater than $79$ since $k\ge 2$.

Way 3

We must ignore the cases where $a_n=1$, as required by the problem statement. Write $a_n=\sqrt{400-k}$ for some integers $k,a_n$. We want to minimize $a_n+n$. Note if $a_n$ is even ($k$ is even) then $n=1.5k+2$, and if $a_n$ is odd ($k$ is odd), then $n=1.5k+1.5$. Rewrite $k=400-a_n^2$ and note that $a_n$ is at most $19$. In the case that $a_n$ is odd, we have $a_n+n=a_n+1.5(400-a_n^2)+1.5$. This is a quadratic in $a_n$ and is strictly decreasing for $a_n>0$, so to minimize we should choose $a_n=19$, which gives $a_n+n=79$. Do the case for $a_n$ even as well, you find that $79$ is the lowest.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_II_2012_Problems/Problem_2&oldid=87691"