Difference between revisions of "2006 AIME II Problems/Problem 11"

(Solution 2)
(Solution)
Line 4: Line 4:
 
== Solution ==
 
== Solution ==
 
Define the sum as <math>s</math>. Since <math>a_n\ = a_{n + 3} - a_{n + 2} - a_{n + 1} </math>, the sum will be:
 
Define the sum as <math>s</math>. Since <math>a_n\ = a_{n + 3} - a_{n + 2} - a_{n + 1} </math>, the sum will be:
<center><math>\begin{align*}s &= a_{28} + \sum^{27}_{k=1} (a_{k+3}-a_{k+2}-a_{k+1}) \
+
<center><math>s = a_{28} + \sum^{27}_{k=1} (a_{k+3}-a_{k+2}-a_{k+1}) \
&= a_{28} + \left(\sum^{30}_{k=4} a_{k} - \sum^{29}_{k=3} a_{k}\right) - \left(\sum^{28}_{k=2} a_{k}\right)\
+
s = a_{28} + \left(\sum^{30}_{k=4} a_{k} - \sum^{29}_{k=3} a_{k}\right) - \left(\sum^{28}_{k=2} a_{k}\right)\
&= a_{28} + (a_{30} - a_{3}) - \left(\sum^{28}_{k=2} a_{k}\right) = a_{28} + a_{30} - a_{3} - (s - a_{1})\
+
s = a_{28} + (a_{30} - a_{3}) - \left(\sum^{28}_{k=2} a_{k}\right) = a_{28} + a_{30} - a_{3} - (s - a_{1})\
&= -s + a_{28} + a_{30}
+
s = -s + a_{28} + a_{30}
\end{align*}</math></center>
+
</math></center>
  
 
Thus <math>s = \frac{a_{28} + a_{30}}{2}</math>, and <math>a_{28},\,a_{30}</math> are both given; the last four digits of their sum is <math>3668</math>, and half of that is <math>1834</math>. Therefore, the answer is <math>\boxed{834}</math>.
 
Thus <math>s = \frac{a_{28} + a_{30}}{2}</math>, and <math>a_{28},\,a_{30}</math> are both given; the last four digits of their sum is <math>3668</math>, and half of that is <math>1834</math>. Therefore, the answer is <math>\boxed{834}</math>.

Revision as of 17:55, 2 March 2015

Problem

A sequence is defined as follows $a_1=a_2=a_3=1,$ and, for all positive integers $n, a_{n+3}=a_{n+2}+a_{n+1}+a_n.$ Given that $a_{28}=6090307, a_{29}=11201821,$ and $a_{30}=20603361,$ find the remainder when $\sum^{28}_{k=1} a_k$ is divided by 1000.

Solution

Define the sum as $s$. Since $a_n\ = a_{n + 3} - a_{n + 2} - a_{n + 1}$, the sum will be:

$s = a_{28} + \sum^{27}_{k=1} (a_{k+3}-a_{k+2}-a_{k+1}) \\ s = a_{28} + \left(\sum^{30}_{k=4} a_{k} - \sum^{29}_{k=3} a_{k}\right) - \left(\sum^{28}_{k=2} a_{k}\right)\\ s = a_{28} + (a_{30} - a_{3}) - \left(\sum^{28}_{k=2} a_{k}\right) = a_{28} + a_{30} - a_{3} - (s - a_{1})\\ s = -s + a_{28} + a_{30}$

Thus $s = \frac{a_{28} + a_{30}}{2}$, and $a_{28},\,a_{30}$ are both given; the last four digits of their sum is $3668$, and half of that is $1834$. Therefore, the answer is $\boxed{834}$.

Solution 2

Brute Force. Since the problem asks for the answer of the end value when divided by 1000, it wouldn't be that difficult because you only need to keep track of the last 3 digits.

See also

2006 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 10
Followed by
Problem 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

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