Difference between revisions of "2015 AMC 12A Problems/Problem 22"
(→Solution 2 (Easy Version)) |
(→Solution 3 (Easy Version)) |
||
Line 40: | Line 40: | ||
==Solution 3 (Easy Version)== | ==Solution 3 (Easy Version)== | ||
− | We can start off by finding patterns in <math>S(n)</math>. 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 <math>S(n) = 2^n - ( | + | We can start off by finding patterns in <math>S(n)</math>. 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 <math>S(n) = 2^n - (n_3) - (n_4)- (n_5) \dots (n_n)</math>. Using the hockey stick identity we realize that the terms aside from <math>2^n</math> are congruent to <math>0</math> mod <math>12</math>. Using patterns we can see that <math>2^2015</math> is congruent to <math>8</math> mod <math>12</math>. Therefore <math>\boxed {8}</math> is our answer. |
== 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 00:20, 23 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 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
. Using the hockey stick identity we realize that the terms aside from
are congruent to
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 |