Difference between revisions of "2015 AMC 12A Problems/Problem 22"
Tigershark22 (talk | contribs) (→Solution) |
(→Solution) |
||
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>. | ||
+ | |||
+ | |||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | We can also go straight to S(2015). We know that there are <math>2^2015</math> permutations if we do not consider the rule of "no three As or Bs in a row". | ||
+ | |||
+ | Now if the rule is considered, Assume that there the 3 As and 3Bs are in the very front. That would yield <math>(1/2)^3 * 2^2012 * 2</math> permutations. Now consider where those three As or three Bs can be placed. There are 2013 places where the consecutive letter can be put. Thus there are <math>2^2015 - 2^2010 * 2013</math> permutations allowed. | ||
+ | |||
+ | Now do some calculation we can know that <math>2^1 \equiv 2\ \text{mod}\ 12</math>, <math>2^2 \equiv 4\ \text{mod}\ 12</math>, <math>2^3 \equiv 8\ \text{mod}\ 12</math>, ... <math>2^2010 \equiv 4\ \text{mod}\ 12</math>, ... <math>2^2015 \equiv 8\ \text{mod}\ 12</math>. Also, from division, <math>2013 \equiv 9\ \text{mod}\ 12</math>. So <math>2^2015 - 2^2010*2013 \equiv 8\ \text{mod}\ 12</math>. | ||
+ | |||
+ | Thus, the answer is <math>\textbf{(D)}</math>. | ||
== 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 11:21, 11 September 2017
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
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 .
Solution 2
We can also go straight to S(2015). We know that there are permutations if we do not consider the rule of "no three As or Bs in a row".
Now if the rule is considered, Assume that there the 3 As and 3Bs are in the very front. That would yield permutations. Now consider where those three As or three Bs can be placed. There are 2013 places where the consecutive letter can be put. Thus there are permutations allowed.
Now do some calculation we can know that , , , ... , ... . Also, from division, . So .
Thus, the answer is .
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 |