Difference between revisions of "2006 AIME II Problems/Problem 11"
(→Solution 2) |
|||
Line 3: | Line 3: | ||
== Solution == | == 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: | 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}) \\ | <center><math>s = a_{28} + \sum^{27}_{k=1} (a_{k+3}-a_{k+2}-a_{k+1}) \\ | ||
Line 13: | Line 13: | ||
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>. | ||
− | ==Solution 2== | + | === Solution 2 === |
Very bad solution: 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. | Very bad solution: 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. | ||
+ | === Solution 3 (some guessing involved) === | ||
+ | All terms in the sequence are sums of previous terms, so the sum of all terms up to a certain point must be some linear combination of the first three terms. Also, we are given <math>a_{28}, a_{29}, </math> and <math>a_{30}</math>, so we can guess that there is some way to use them in a formula. Namely, we guess that there exists some <math>p, q, r</math> such that <math>\sum_{k=1}^{n}{a_k} = pa_n+qa_{n+1}+ra_{n+2}</math>. From here, we list out the first few terms of the sequence and the cumulative sums, and with a little bit of substitution and algebra we see that <math>(p, q, r) = (\frac{1}{2}, 0, \frac{1}{2})</math>, at least for the first few terms. From this, we have that <math>\sum_{k=1}^{28}{a_k} = \frac{a_{28}+a_{30}}{2} \equiv{\boxed{834}}(\mod 1000)</math>. | ||
+ | |||
+ | Solution by zeroman | ||
== See also == | == See also == | ||
{{AIME box|year=2006|n=II|num-b=10|num-a=12}} | {{AIME box|year=2006|n=II|num-b=10|num-a=12}} |
Revision as of 22:33, 21 March 2018
Contents
Problem
A sequence is defined as follows and, for all positive integers
Given that
and
find the remainder when
is divided by 1000.
Solution
Solution 1
Define the sum as . Since
, 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}$](http://latex.artofproblemsolving.com/2/a/d/2ad278b512318ab58fc7ef7280e03bd129453fe1.png)
Thus , and
are both given; the last four digits of their sum is
, and half of that is
. Therefore, the answer is
.
Solution 2
Very bad solution: 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.
Solution 3 (some guessing involved)
All terms in the sequence are sums of previous terms, so the sum of all terms up to a certain point must be some linear combination of the first three terms. Also, we are given and
, so we can guess that there is some way to use them in a formula. Namely, we guess that there exists some
such that
. From here, we list out the first few terms of the sequence and the cumulative sums, and with a little bit of substitution and algebra we see that
, at least for the first few terms. From this, we have that
.
Solution by zeroman
See also
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.