Difference between revisions of "2015 AMC 12A Problems/Problem 22"
(→Recursion Solution II) |
(New solution) |
||
Line 37: | Line 37: | ||
From there we realize that <math>S(n)=S(n-1)+S(n-2)+S(n-3)</math> because 3 in a row requires <math>S(n-3)</math>, and so on. Let's start using all <math>S(n)</math> values <math>(\mod12)</math>. We also know that <math>S(1)=2, S(2)=4, S(3)=8</math>, and so on. These residues are: <math>2, 4, 8, 2, 2, 0, 4, 6, 10, 8, 0, 6, 2, 8, 4, 2, 2, 8...</math>, upon which the cycle repeats. Note that the cycle length is 52, and <math>2015=38\cdot 52+39</math>, so the residue of <math>S(2015)(\mod{12})</math> is the residue of <math>S(39)=\boxed{8}</math>. | From there we realize that <math>S(n)=S(n-1)+S(n-2)+S(n-3)</math> because 3 in a row requires <math>S(n-3)</math>, and so on. Let's start using all <math>S(n)</math> values <math>(\mod12)</math>. We also know that <math>S(1)=2, S(2)=4, S(3)=8</math>, and so on. These residues are: <math>2, 4, 8, 2, 2, 0, 4, 6, 10, 8, 0, 6, 2, 8, 4, 2, 2, 8...</math>, upon which the cycle repeats. Note that the cycle length is 52, and <math>2015=38\cdot 52+39</math>, so the residue of <math>S(2015)(\mod{12})</math> is the residue of <math>S(39)=\boxed{8}</math>. | ||
+ | |||
+ | ==Solution(Easy Version)== | ||
+ | We can start off by finding patterns in S(n). When we calculate a few values we realize either from performing the calculation or because the calculation was performed in the exact same way that S(n) = 2^n - (n 3) - (n 4)- (n 5).....(n n). Using the hockey stick identity we realize that the terms aside from 2^n are congruent to 0 mod 12. Using patterns we can see that 2^2015 is congruent to 8 mod 12 and 8 is our answer. Also can someone please clean this up with LATEX. | ||
== See Also == | == See Also == | ||
{{AMC12 box|year=2015|ab=A|num-b=21|num-a=23}} | {{AMC12 box|year=2015|ab=A|num-b=21|num-a=23}} |
Revision as of 20:04, 22 December 2019
Problem
For each positive integer , let
be the number of sequences of length
consisting solely of the letters
and
, with no more than three
s in a row and no more than three
s in a row. What is the remainder when
is divided by
?
Solution
One method of approach is to find a recurrence for .
Let us define as the number of sequences of length
ending with an
, and
as the number of sequences of length
ending in
. Note that
and
, so
.
For a sequence of length ending in
, it must be a string of
s appended onto a sequence ending in
of length
. So we have the recurrence:
We can thus begin calculating values of . We see that the sequence goes (starting from
):
A problem arises though: the values of increase at an exponential rate. Notice however, that we need only find
. In fact, we can use the fact that
to only need to find
. Going one step further, we need only find
and
to find
.
Here are the values of , starting with
:
Since the period is and
,
.
Similarly, here are the values of , starting with
:
Since the period is and
,
.
Knowing that and
, we see that
, and
. Hence, the answer is
.
- Note that instead of introducing
and
, we can simply write the relation
and proceed as above.
Recursion Solution II
The huge value in place, as well as the "no more than... in a row" are key phrases that indicate recursion is the right way to go.
Let's go with finding the case of
from previous cases.
So how can we make the words of
? Do we choose 3-in-a-row of one letter,
or
, or do we want 2 consecutive ones or 1? Note that this covers all possible cases of ending with
and
with a certain number of consecutive letters. And obviously they are all distinct.
[Convince yourself that each case for is considered exactly once by using these cues: does it end in 3, 2, or 1 consecutive letter(s) (1 consecutive means a string like ...BA, ...AB, as in the letter switches) and does it WLOG consider both A and B?]
From there we realize that because 3 in a row requires
, and so on. Let's start using all
values
. We also know that
, and so on. These residues are:
, upon which the cycle repeats. Note that the cycle length is 52, and
, so the residue of
is the residue of
.
Solution(Easy Version)
We can start off by finding patterns in S(n). When we calculate a few values we realize either from performing the calculation or because the calculation was performed in the exact same way that S(n) = 2^n - (n 3) - (n 4)- (n 5).....(n n). Using the hockey stick identity we realize that the terms aside from 2^n are congruent to 0 mod 12. Using patterns we can see that 2^2015 is congruent to 8 mod 12 and 8 is our answer. Also can someone please clean this up with LATEX.
See Also
2015 AMC 12A (Problems • Answer Key • Resources) | |
Preceded by Problem 21 |
Followed by Problem 23 |
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 |