Difference between revisions of "2015 AMC 12A Problems/Problem 22"
(→Recursion Solution II) |
m (→Solution 3 (Easy Version)) |
||
(11 intermediate revisions by 4 users not shown) | |||
Line 5: | Line 5: | ||
<math>\textbf{(A)}\ 0\qquad\textbf{(B)}\ 4\qquad\textbf{(C)}\ 6\qquad\textbf{(D)}\ 8\qquad\textbf{(E)}\ 10 </math> | <math>\textbf{(A)}\ 0\qquad\textbf{(B)}\ 4\qquad\textbf{(C)}\ 6\qquad\textbf{(D)}\ 8\qquad\textbf{(E)}\ 10 </math> | ||
− | ==Solution== | + | ==Solution 1== |
One method of approach is to find a recurrence for <math>S(n)</math>. | One method of approach is to find a recurrence for <math>S(n)</math>. | ||
Line 29: | Line 29: | ||
* Note that instead of introducing <math>A(n)</math> and <math>B(n)</math>, we can simply write the relation <math>S(n)=S(n-1)+S(n-2)+S(n-3),</math> and proceed as above. | * Note that instead of introducing <math>A(n)</math> and <math>B(n)</math>, we can simply write the relation <math>S(n)=S(n-1)+S(n-2)+S(n-3),</math> and proceed as above. | ||
− | ==Recursion Solution | + | ==Recursion Solution 2== |
The huge <math>n</math> 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. | The huge <math>n</math> 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 <math>S(n)</math> from previous cases. | Let's go with finding the case of <math>S(n)</math> from previous cases. | ||
− | So how can we make the words of <math>S(n)</math>? Do we choose 3-in-a-row of one letter, <math>A</math> or <math>B</math>, or do we want 2 consecutive ones or 1? Note that this covers all possible cases of ending with <math>A</math> and <math>B</math> with a certain number of consecutive letters. And obviously they are all distinct. | + | So how can we make the words of <math>S(n)</math>? Do we choose 3-in-a-row of one letter, <math>A</math> or <math>B</math>, or do we want <math>2</math> consecutive ones or <math>1</math>? Note that this covers all possible cases of ending with <math>A</math> and <math>B</math> with a certain number of consecutive letters. And obviously they are all distinct. |
− | [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 <math>3</math>, <math>2</math>, or <math>1</math> consecutive letter(s) (<math>1</math> consecutive means a string like ...<math>BA</math>, ...<math>AB</math>, as in the letter switches) and does it <math>WLOG</math> consider both <math>A</math> and <math>B?</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 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) = | + | 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 <math>4</math>. By listing out the residues mod <math>3</math>, we find that the cycle length for mod <math>3</math> is <math>13</math>. <math>2015</math> is <math>0</math> mod <math>13</math> so <math>S(2015) = S(13) = 2</math> mod <math>3</math>. By listing out the residues mod <math>4</math>, we find that the cycle length for mod <math>4</math> is <math>4</math>. S(2015) = S(3) = mod <math>4</math>. By Chinese Remainder Theorem, <math>S(2015) =\boxed{8}</math> mod <math>12</math>. |
==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 - 2((n_4)- (n_5) \dots (n_n))</math>. Rearranging the expression we realize that the terms aside from <math>2^2015</math> are congruent to <math>0</math> mod <math>12</math>(Just put the equation in terms of 2^{2015} and the four combinations excluded and calculate the combinations 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. | + | 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 - 2((n_4)- (n_5) \dots (n_n))</math>. Rearranging the expression we realize that the terms aside from <math>2^{2015}</math> are congruent to <math>0</math> mod <math>12</math>(Just put the equation in terms of <math>2^{2015}</math> and the four combinations excluded and calculate the combinations 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. |
+ | ~Very minor edit in LaTeX by get-rickrolled | ||
+ | |||
+ | == Video Solution by Richard Rusczyk == | ||
+ | |||
+ | https://artofproblemsolving.com/videos/amc/2015amc12a/400 | ||
+ | |||
+ | ~ dolphin7 | ||
== 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}} |
Latest revision as of 13:08, 5 May 2024
Contents
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 1
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 2
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
consecutive ones or
? 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
,
, or
consecutive letter(s) (
consecutive means a string like ...
, ...
, as in the letter switches) and does it
consider both
and
]
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
. By listing out the residues mod
, we find that the cycle length for mod
is
.
is
mod
so
mod
. By listing out the residues mod
, we find that the cycle length for mod
is
. S(2015) = S(3) = mod
. By Chinese Remainder Theorem,
mod
.
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
and the four combinations excluded and calculate the combinations mod
). Using patterns we can see that
is congruent to
mod
. Therefore
is our answer.
~Very minor edit in LaTeX by get-rickrolled
Video Solution by Richard Rusczyk
https://artofproblemsolving.com/videos/amc/2015amc12a/400
~ dolphin7
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 |