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

Revision as of 22:54, 16 January 2017

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

Solution 1

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.

@@ Line 3: / Line 3: @@
 == Solution ==
-==Solution 1
+==Solution 1==
 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>s = a_{28} + \sum^{27}_{k=1} (a_{k+3}-a_{k+2}-a_{k+1}) \\

2006 AIME II (Problems • Answer Key • Resources)
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

Page

Toolbox

Search