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 "2009 AMC 12A Problems/Problem 25"

(→‎Clarification of Solution 1)
Line 31: Line 31:
 
Our answer is <math>|a_{2009}| = \boxed{\textbf{(A)}\ 0}</math>.
 
Our answer is <math>|a_{2009}| = \boxed{\textbf{(A)}\ 0}</math>.
  
−
==Solution 2==
+
==Clarification==
−
(This is for the brute force users; kudos to the very intuitive solution above)
+
(While the above solution is quite intuitive, it's kinda hard for people who don't know many proofing symbols to understand.)
−
 
 
−
First we interpret the formula:
 
−
 
 
−
"The next term in the sequence is equivalent to the sum of the previous two divided by 1 minus their product"
 
−
 
 
−
Next, we work out the first few terms of the sequence:
 
−
 
 
−
 
 
−
<math>a_3 = \frac{1 + \frac{ \sqrt{3} } {3} } {1-\frac{\sqrt{3}}{3}}</math>
 
−
 
 
−
 
 
−
<math>\Rightarrow \frac{3+\sqrt{3}}{3-\sqrt{3}}</math>
 
−
 
 
−
 
 
−
<math>\Rightarrow 2 + \sqrt{3}</math>
 
−
 
 
−
 
 
−
<math>a_4 = \frac{\frac{\sqrt{3}}{3}+2+\sqrt{3}}{1-\frac{\sqrt{3}(2+\sqrt{3})}{3}}</math>
 
−
 
 
−
 
 
−
<math>\Rightarrow \frac{6+4\sqrt{3}}{-2\sqrt{3}}</math>
 
−
 
 
−
 
 
−
<math>\Rightarrow -(2+\sqrt{3})</math>
 
−
 
 
−
 
 
−
So at this point, our sequence reads
 
−
 
 
−
 
 
−
<math>1,\: \frac{\sqrt{3}}{3}, \: 2 + \sqrt{3}, \: -(2+\sqrt{3})</math>
 
−
 
 
−
 
 
−
Now for <math>a_5</math>..... but wait! the numerator of the next term is equal to <math>2 + \sqrt{3} + -(2+\sqrt{3})</math>..... <math>\Rightarrow 0</math>. So as long as the denominator isn't <math>0</math> (which we can quickly verify), <math>a_5 = 0</math>. Now our sequence is
 
−
 
 
−
 
 
−
<math>1,\: \frac{\sqrt{3}}{3}, \: 2 + \sqrt{3}, \: -(2+\sqrt{3}), \: 0</math>
 
−
 
 
−
 
 
−
Solving for <math>a_6</math>:
 
−
 
 
−
 
 
−
<math>\frac{-(2+\sqrt{3})+0}{1-0}</math>
 
−
 
 
−
 
 
−
<math>\Rightarrow -(2+\sqrt{3})</math>
 
−
 
 
−
 
 
−
Our sequence is now
 
−
 
 
−
 
 
−
<math>1,\: \frac{\sqrt{3}}{3}, \: 2 + \sqrt{3}, \: -(2+\sqrt{3}), \: 0, \: -(2+\sqrt{3})</math>
 
−
 
 
−
 
 
−
Solving in this way until <math>a_</math>
 
−
 
 
−
 
 
−
The problem asks us for the value of <math>a_{2009}</math>, and since <math>2009</math> is an odd number, we know that <math>a_{2009} = 0 \Rightarrow \boxed{\text{E}}</math>.
 
−
 
 
−
 
 
−
==Clarification of Solution 1==
 
−
(While I did say the first solution is intuitive, it's kinda hard for people with just a basic knowledge of math, and no knowledge of proofing symbols to understand.)
 
  
  
Line 154: Line 93:
  
  
−
But wait... we're dealing with the <math>\tan</math> function, which has a period (recurrence rate) of <math>2\pi</math> or <math>180^{\circ}</math>. Since we divided the angle measures by <math>15</math>, the period is now <math>12</math> (which aligns with what we got earlier: <math>a_5 = 0</math>). This means that we can reduce the terms of the sequence based on the <math>\bmod</math> function, which returns the remainder after dividing by a certain amount. So now we can say <math>b_n \equiv b_n \bmod{12}</math>. Now we continue our sequence:
+
But wait... we're dealing with the <math>\tan</math> function, which has a period (recurrence rate) of <math>2\pi</math> or <math>180^{\circ}</math>. Since we divided the angle measures by <math>15</math>, the period is now <math>12</math> (which aligns with what we got earlier: <math>a_5 = 0</math>). This means that we can reduce the terms of the sequence based on the <math>\bmod</math> function, which returns the remainder after dividing by a certain amount. So now we can say <math>b_n \equiv b_n \bmod{12}</math> (<math>\equiv</math> denotes modular equivalence in this context). Now we continue our sequence:
  
 
<math>3, 2, 5, 7, 0, 7, 7, 2, 9, 11, 8, 7, 3, 10, 1, 11, 0, 11, 11, 10, 9, 7, 4, 11, 3, 2, 5</math> (It's starting to repeat now)
 
<math>3, 2, 5, 7, 0, 7, 7, 2, 9, 11, 8, 7, 3, 10, 1, 11, 0, 11, 11, 10, 9, 7, 4, 11, 3, 2, 5</math> (It's starting to repeat now)
  
−
So <math>a_1  = 3, a_25 = 3, a_49 = 3</math>, and so on. The sequence repeats every 24 terms
+
So <math>a_1  = 3, a_25 = 3, a_49 = 3</math>, and so on. The sequence repeats every <math>24</math> terms. The problem asks us for the value of <math>a_{2009}</math>. Let's whip out the <math>\bmod</math> function again.
 +
 
 +
 
 +
<math>2009 \bmod 24 = 17</math>
 +
 
 +
 
 +
So we want the value of the <math>17</math> number in the sequence and looking back at it (hopefully you wrote it down somewhere) we find that
  
 
== See also ==
 
== See also ==

Revision as of 10:54, 30 July 2020

Problem

The first two terms of a sequence are $a_1 = 1$ and $a_2 = \frac {1}{\sqrt3}$. For $n\ge1$,

\[a_{n + 2} = \frac {a_n + a_{n + 1}}{1 - a_na_{n + 1}}.\]

What is $|a_{2009}|$?

$\textbf{(A)}\ 0\qquad \textbf{(B)}\ 2 - \sqrt3\qquad \textbf{(C)}\ \frac {1}{\sqrt3}\qquad \textbf{(D)}\ 1\qquad \textbf{(E)}\ 2 + \sqrt3$

Solution

Consider another sequence $\{\theta_1, \theta_2, \theta_3...\}$ such that $a_n = \tan{\theta_n}$, and $0 \leq \theta_n < 180$.

The given recurrence becomes

\begin{align*} a_{n + 2} & = \frac {a_n + a_{n + 1}}{1 - a_na_{n + 1}} \\ \tan{\theta_{n + 2}} & = \frac {\tan{\theta_n} + \tan{\theta_{n + 1}}}{1 - \tan{\theta_n}\tan{\theta_{n + 1}}} \\ \tan{\theta_{n + 2}} & = \tan(\theta_{n + 1} + \theta_n) \end{align*}

It follows that $\theta_{n + 2} \equiv \theta_{n + 1} + \theta_{n} \pmod{180}$. Since $\theta_1 = 45, \theta_2 = 30$, all terms in the sequence $\{\theta_1, \theta_2, \theta_3...\}$ will be a multiple of $15$.

Now consider another sequence $\{b_1, b_2, b_3...\}$ such that $b_n = \theta_n/15$, and $0 \leq b_n < 12$. The sequence $b_n$ satisfies $b_1 = 3, b_2 = 2, b_{n + 2} \equiv b_{n + 1} + b_n \pmod{12}$.

As the number of possible consecutive two terms is finite, we know that the sequence $b_n$ is periodic. Write out the first few terms of the sequence until it starts to repeat.

$\{b_n\} = \{3,2,5,7,0,7,7,2,9,11,8,7,3,10,1,11,0,11,11,10,9,7,4,11,3,2,5,7,...\}$

Note that $b_{25} = b_1 = 3$ and $b_{26} = b_2 = 2$. Thus $\{b_n\}$ has a period of $24$: $b_{n + 24} = b_n$.

It follows that $b_{2009} = b_{17} = 0$ and $\theta_{2009} = 15 b_{2009} = 0$. Thus $a_{2009} = \tan{\theta_{2009}} = \tan{0} = 0.$

Our answer is $|a_{2009}| = \boxed{\textbf{(A)}\ 0}$.

Clarification

(While the above solution is quite intuitive, it's kinda hard for people who don't know many proofing symbols to understand.)


Notice that the formula looks incredibly similar to the Tangent Addition Formula

Since $a_1 = 1$, let $a_1$ be $\tan{45}$. Similarly, let $a_2$ be $\tan{30}$. Then the formula reads


\[a_3 = \frac {\tan{45} + \tan{30} }{1 - \tan{45}*\tan{30}}.\]


But from the Tangent Addition Formula we know that this is the formula for $\tan{(45+30)}$ or $\tan{75}$, meaning $a_3 = \tan{75}$. So, the sequence is simply the sum of the two angle measures. We continue to sum angle measures, like so:


$a_4 = \tan{(75+30)} = \tan{105}$


$a_5 = \tan{(105+75)} = \tan{180}$


$a_6 = \tan{(180+105)} =$ ... wait a minute! $\tan{180} = \tan{0}$!


So now we have


$a_5 = \tan{0}$


$a_6 = \tan{(105+0)} = \tan{105}$


$a_7 = \tan{(105+105)} = \tan{210}$


$a_8 = \tan{(210+105)} =$ .... Ok this is getting tiring. Let's stop and think about whether we can simplify this. Notice that all of the angle measures are a multiple of $15$. Let's express the angle measures as multiples of $15$.


Let $b_n = \frac{\arctan{(a_n)}}{15}$.


(Basically, $b_n$ is the angle measure of the corresponding $a_n$, divided by $15$)

Now we have


$b_1 = 3$


$b_2 = 2$


$b_3 = 5$


$b_4 = 7$


$b_5 = 12$


But wait... we're dealing with the $\tan$ function, which has a period (recurrence rate) of $2\pi$ or $180^{\circ}$. Since we divided the angle measures by $15$, the period is now $12$ (which aligns with what we got earlier: $a_5 = 0$). This means that we can reduce the terms of the sequence based on the $\bmod$ function, which returns the remainder after dividing by a certain amount. So now we can say $b_n \equiv b_n \bmod{12}$ ($\equiv$ denotes modular equivalence in this context). Now we continue our sequence:

$3, 2, 5, 7, 0, 7, 7, 2, 9, 11, 8, 7, 3, 10, 1, 11, 0, 11, 11, 10, 9, 7, 4, 11, 3, 2, 5$ (It's starting to repeat now)

So $a_1 = 3, a_25 = 3, a_49 = 3$, and so on. The sequence repeats every $24$ terms. The problem asks us for the value of $a_{2009}$. Let's whip out the $\bmod$ function again.


$2009 \bmod 24 = 17$


So we want the value of the $17$ number in the sequence and looking back at it (hopefully you wrote it down somewhere) we find that

See also

2009 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 24 		Followed by
Last question
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_AMC_12A_Problems/Problem_25&oldid=129822"