Difference between revisions of "2015 AIME II Problems/Problem 12"
Line 3: | Line 3: | ||
There are <math>2^{10} = 1024</math> 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. | There are <math>2^{10} = 1024</math> 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== | + | ==Solution 1== |
The solution is a simple recursion: | The solution is a simple recursion: | ||
Line 28: | Line 28: | ||
<math>a_{10}=88</math>, <math>b_{10}=162</math>, and <math>c_{10}=298</math>. | <math>a_{10}=88</math>, <math>b_{10}=162</math>, and <math>c_{10}=298</math>. | ||
Summing the three up we have our solution: <math>88+162+298=548</math>. | Summing the three up we have our solution: <math>88+162+298=548</math>. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | This is a recursion problem. Let <math>a_n</math> be the number of valid strings of <math>n</math> letters, where the first letter is <math>A</math>. Similarly, let <math>b_n</math> be the number of valid strings of <math>n</math> letters, where the first letter is <math>B</math>. | ||
+ | |||
+ | Note that <math>a_n=b_{n-1}+b_{n-2}+b_{n-3}</math> for all <math>n\ge4</math>. | ||
+ | |||
+ | Similarly, we have <math>b_n=a_{n-1}+a_{n-2}+a_{n-3}</math> for all <math>n\ge4</math>. | ||
+ | |||
+ | Here is why: every valid strings of <math>n</math> letters <math>(n\ge4)</math> where the first letter is <math>A</math> must begin with one of the following: | ||
+ | |||
+ | <math>AAAB</math> - and the number of valid ways is <math>b_{n-3}</math>. | ||
+ | |||
+ | <math>AAB</math> - and the number of valid ways is <math>b_{n-2}</math>. | ||
+ | |||
+ | <math>AB</math> - and there are <math>b_{n-1}</math> ways. | ||
+ | |||
+ | We know that <math>a_1=1</math>, <math>a_2=2</math>, and <math>a_3=4</math>. Similarly, we have <math>b_1=1</math>, <math>b_2=2</math>, and <math>b_3=4</math>. We can quickly check our recursion to see if our recursive formula works. By the formula, <math>a_4=b_3+b_2+b_1=7</math>, and listing out all <math>a_4</math>, we can quickly verify our formula. | ||
+ | |||
+ | Therefore, we have the following: | ||
+ | |||
+ | <math> | ||
+ | |||
+ | The total number of valid <math>10</math> letter strings is equal to <math>a_{10}+b_{10}=274+274=\boxed{548}</math>. | ||
==See also== | ==See also== | ||
{{AIME box|year=2015|n=II|num-b=11|num-a=13}} | {{AIME box|year=2015|n=II|num-b=11|num-a=13}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 10:16, 27 March 2015
Contents
[hide]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 1
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: .
Solution 2
This is a recursion problem. Let be the number of valid strings of letters, where the first letter is . Similarly, let be the number of valid strings of letters, where the first letter is .
Note that for all .
Similarly, we have for all .
Here is why: every valid strings of letters where the first letter is must begin with one of the following:
- and the number of valid ways is .
- and the number of valid ways is .
- and there are ways.
We know that , , and . Similarly, we have , , and . We can quickly check our recursion to see if our recursive formula works. By the formula, , and listing out all , we can quickly verify our formula.
Therefore, we have the following:
The total number of valid letter strings is equal to .
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.