Difference between revisions of "2015 AMC 12A Problems/Problem 22"
(→Recursion Solution II) |
(→Recursion Solution II) |
||
Line 36: | Line 36: | ||
[Convince yourself that each case for <math>S(n)</math> 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?] | [Convince yourself that each case for <math>S(n)</math> 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 <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. We need to find <math>S(2015)</math> mod 12. We first compute <math>S(2015)</math> mod 3 and mod 4. By listing out the residues mod 3, we find that the cycle length for mod 3 is 13. 2015 is 0 mod 13 so <math>S(2015) = S(13) = 2</math> mod 3. By listing out the residues mod 4, we find that the cycle length for mod 4 is 4. S(2015) = S(3) = (\mod {4})<math>. By Chinese Remainder Theorem, S(2015) </math>=\boxed{8}<math> (\mod {12})</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. We need to find <math>S(2015)</math> mod 12. We first compute <math>S(2015)</math> mod <math>3</math> and mod 4. By listing out the residues mod 3, we find that the cycle length for mod 3 is 13. 2015 is 0 mod 13 so <math>S(2015) = S(13) = 2</math> mod 3. By listing out the residues mod 4, we find that the cycle length for mod 4 is 4. S(2015) = S(3) = (\mod {4})<math>. By Chinese Remainder Theorem, S(2015) </math>=\boxed{8}<math> (\mod {12})</math>. |
==Solution 3 (Easy Version)== | ==Solution 3 (Easy Version)== |
Revision as of 15:42, 26 January 2020
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. We need to find
mod 12. We first compute
mod
and mod 4. By listing out the residues mod 3, we find that the cycle length for mod 3 is 13. 2015 is 0 mod 13 so
mod 3. By listing out the residues mod 4, we find that the cycle length for mod 4 is 4. S(2015) = S(3) = (\mod {4})
=\boxed{8}
.
Solution 3 (Easy Version)
We can start off by finding patterns in . 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
. Rearranging the expression we realize that the terms aside from
are congruent to
mod
(Just put the equation in terms of 2^{2015} and the four combinations excluded and calculate the combinations mod
). Using patterns we can see that
is congruent to
mod
. Therefore
is our answer.
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 |