Difference between revisions of "2015 AIME II Problems/Problem 12"
(→Solution) |
|||
| Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
| − | |||
The solution is a simple recursion: | The solution is a simple recursion: | ||
| Line 10: | Line 9: | ||
We have three cases for the ending of a string: three in a row, two in a row, and a single: | We have three cases for the ending of a string: three in a row, two in a row, and a single: | ||
| − | ...AAA (1) | + | ...AAA <math>(1)</math> |
| − | ...BAA (2) | + | ...BAA <math>(2)</math> |
| − | ...BBA (3) | + | ...BBA <math>(3)</math> |
| − | For case (1), we could only add a B to the end, making it a case (3). | + | For case <math>(1)</math>, we could only add a B to the end, making it a case <math>(3)</math>. |
| − | For case (2), we could add an A or a B to the end, making it a case (1) if you add an A, or a case (3) if you add a B. | + | For case <math>(2)</math>, we could add an A or a B to the end, making it a case <math>(1)</math> if you add an A, or a case <math>(3)</math> if you add a B. |
| − | For case (3), we could add an A or a B to the end, making it a case (2) or a case (3). | + | For case <math>(3)</math>, we could add an A or a B to the end, making it a case <math>(2)</math> or a case <math>(3)</math>. |
| − | Let us create three series to represent the number of permutations for each case: {a}, {b}, and {c} representing case (1), (2), and (3) respectively. | + | Let us create three series to represent the number of permutations for each case: <math>\{a\}</math>, <math>\{b\}</math>, and <math>\{c\}</math> representing case <math>(1)</math>, <math>(2)</math>, and <math>(3)</math> respectively. |
The series have the following relationship: | The series have the following relationship: | ||
| − | + | <math>a_n=b_{n-1}</math> | |
| − | + | <math>b_n=c_{n-1}</math> | |
| − | + | <math>c_n=c_{n-1}+a_{n-1}+b_{n-1}</math> | |
| − | + | For <math>n=3</math>: <math>a_3</math> and <math>b_3</math> both equal <math>2</math>, <math>c_3=4</math>. With some simple math, we have: | |
| − | + | <math>a_{10}=88</math>, <math>b_{10}=162</math>, and <math>c_{10}=298</math>. | |
| − | Summing the three up we have our solution: 88 + 162 + 298 = 548. | + | Summing the three up we have our solution: <math>88+162+298=548</math>. |
| + | |||
| + | ==See also== | ||
| + | {{AIME box|year=2015|n=II|num-b=11|num-a=13}} | ||
| + | {{MAA Notice}} | ||
Revision as of 09:26, 27 March 2015
Problem
There are 
possible 10-letter strings in which each letter is either an A or a B. Find the number of such strings that do not have more than 3 adjacent letters that are identical.
Solution
The solution is a simple recursion:
We have three cases for the ending of a string: three in a row, two in a row, and a single:
...AAA 
...BAA 
...BBA 
For case , we could only add a B to the end, making it a case .
For case , we could add an A or a B to the end, making it a case if you add an A, or a case if you add a B.
For case , we could add an A or a B to the end, making it a case or a case .
Let us create three series to represent the number of permutations for each case: 
, 
, and 
representing case , , and respectively.
The series have the following relationship:
For 
: 
and 
both equal 
, 
. With some simple math, we have:
, 
, and 
.
Summing the three up we have our solution: 
.
See also
| 2015 AIME II (Problems • Answer Key • Resources) | ||
| Preceded by Problem 11 |
Followed by Problem 13 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
