2015 AIME II Problems/Problem 12
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.
Let be the number of ways to form -letter strings made up of As and Bs such that no more than adjacent letters are identical.
Note that, at the end of each -letter string, there are possibilities for the last letter chain: it must be either , , or letters long. Removing this last chain will make a new string that is , , or letters long, respectively.
Therefore we can deduce that .
We can see that so using our recursive relation we find
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 or ...ABA
(Here, WLOG each string ends with A. This won't be the case when we actually solve for values in recursion.)
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: .
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 .
Notice that , since , , and . Therefore, we didn't really need to list out both recursion formulas, which could save us some time.
Solution 4 (Without Recursion)
Playing around with strings gives this approach: We have a certain number of As, then Bs, and so on. Therefore, what if we denoted each solution with numbers like to denote AAABBBAAAB or vice versa (starting with Bs)? Every string can be represented like this!
We can have from 4 to 10 numbers in our parentheses. For each case, we will start with the largest number possible, usually a bunch of 3s, then go down systematically. Realize also that if we are left with just 2s and 1s, there is only one number of 2s and 1s that adds up to the leftover amount. Our final answer is the sum of all of these parenthetical sets [each set multiplied by its permutations, as order matters] multiplied by two [starting with either A or B, and alternating as we go along].
Adding them all up gives you 274; multiplying by 2 gives .
We are going to build the string, 1 character at a time. And, we are going to only care about the streak of letters at the end of the string.
Let be the number of strings of length n that satisfy the problem statement and also has a "streak" of length 1 at the end. ABABBA has a streak of length 1.
Let be the number of strings of length n that satisfy the problem statement and also has of length 2 at the end. ABABBAA has a streak of length 2. There are 2 "A" s at the end of the string.
Let be the number of string of length n that that satisfy the problem statement and also has a "streak" of length 3 at the end. ABABBAAA has a streak of length 3. There are 3 "A" s at the end of the string.
Let's establish a recursive relationship. , since you can simply break the streak. , and Since you can just add to the streak.
We can log everything using a table.
Adding , , gets the total number of numbers that doesn't have more than 3 concecutive letters.
That gets a total of
|2015 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|