Difference between revisions of "2015 AMC 12A Problems/Problem 22"
m (→Solution) |
m (→Solution 3 (Easy Version)) |
||
(41 intermediate revisions by 16 users not shown) | |||
Line 1: | Line 1: | ||
==Problem== | ==Problem== | ||
− | For each positive integer <math>n</math>, let <math>S(n)</math> be the number of sequences of length <math>n</math> consisting solely of the letters <math>A</math> and <math>B</math>, with no more than three <math>A</math>s in a row and no more than three <math>B</math>s in a row. What is the remainder when <math>S(2015)</math> is divided by 12? | + | For each positive integer <math>n</math>, let <math>S(n)</math> be the number of sequences of length <math>n</math> consisting solely of the letters <math>A</math> and <math>B</math>, with no more than three <math>A</math>s in a row and no more than three <math>B</math>s in a row. What is the remainder when <math>S(2015)</math> is divided by <math>12</math>? |
− | <math> \textbf{(A)}\ 0\qquad\textbf{(B)}\ 4\qquad\textbf{(C)}\ 6\qquad\textbf{(D) | + | <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 11: | Line 11: | ||
Let us define <math>A(n)</math> as the number of sequences of length <math>n</math> ending with an <math>A</math>, and <math>B(n)</math> as the number of sequences of length <math>n</math> ending in <math>B</math>. Note that <math>A(n) = B(n)</math> and <math>S(n) = A(n) + B(n)</math>, so <math>S(n) = 2A(n)</math>. | Let us define <math>A(n)</math> as the number of sequences of length <math>n</math> ending with an <math>A</math>, and <math>B(n)</math> as the number of sequences of length <math>n</math> ending in <math>B</math>. Note that <math>A(n) = B(n)</math> and <math>S(n) = A(n) + B(n)</math>, so <math>S(n) = 2A(n)</math>. | ||
− | For a sequence of length <math>n</math> ending in <math>A</math>, it must be a string of <math>A</math>s appended onto a sequence ending in <math>B</math> of length <math>n-1, n-2, \text{or}\ n-3</math>. So we have the recurrence <cmath>A(n) = B(n-1) + B(n-2) + B(n-3) = A(n-1) + A(n-2) + A(n-3) | + | For a sequence of length <math>n</math> ending in <math>A</math>, it must be a string of <math>A</math>s appended onto a sequence ending in <math>B</math> of length <math>n-1, n-2, \text{or}\ n-3</math>. So we have the recurrence: <cmath>A(n) = B(n-1) + B(n-2) + B(n-3) = A(n-1) + A(n-2) + A(n-3)</cmath> |
We can thus begin calculating values of <math>A(n)</math>. We see that the sequence goes (starting from <math>A(0) = 1</math>): <math>1,1,2,4,7,13,24...</math> | We can thus begin calculating values of <math>A(n)</math>. We see that the sequence goes (starting from <math>A(0) = 1</math>): <math>1,1,2,4,7,13,24...</math> | ||
− | A problem arises though | + | A problem arises though: the values of <math>A(n)</math> increase at an exponential rate. Notice however, that we need only find <math>S(2015)\ \text{mod}\ 12</math>. In fact, we can use the fact that <math>S(n) = 2A(n)</math> to only need to find <math>A(2015)\ \text{mod}\ 6</math>. Going one step further, we need only find <math>A(2015)\ \text{mod}\ 2</math> and <math>A(2015)\ \text{mod}\ 3</math> to find <math>A(2015)\ \text{mod}\ 6</math>. |
Here are the values of <math>A(n)\ \text{mod}\ 2</math>, starting with <math>A(0)</math>: <cmath>1,1,0,0,1,1,0,0...</cmath> | Here are the values of <math>A(n)\ \text{mod}\ 2</math>, starting with <math>A(0)</math>: <cmath>1,1,0,0,1,1,0,0...</cmath> | ||
Line 26: | Line 26: | ||
Knowing that <math>A(2015) \equiv 0\ \text{mod}\ 2</math> and <math>A(2015) \equiv 1\ \text{mod}\ 3</math>, we see that <math>A(2015) \equiv 4\ \text{mod}\ 6</math>, and <math>S(2015) \equiv 8\ \text{mod}\ 12</math>. Hence, the answer is <math>\textbf{(D)}</math>. | Knowing that <math>A(2015) \equiv 0\ \text{mod}\ 2</math> and <math>A(2015) \equiv 1\ \text{mod}\ 3</math>, we see that <math>A(2015) \equiv 4\ \text{mod}\ 6</math>, and <math>S(2015) \equiv 8\ \text{mod}\ 12</math>. Hence, the answer is <math>\textbf{(D)}</math>. | ||
+ | |||
+ | * 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 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. | ||
+ | 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 <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 <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 <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)== | ||
+ | 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 == | ||
+ | {{AMC12 box|year=2015|ab=A|num-b=21|num-a=23}} |
Latest revision as of 12:08, 5 May 2024
Contents
[hide]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 |