2003 AIME II Problems/Problem 3
Define a as a sequence of letters that consists only of the letters , , and - some of these letters may not appear in the sequence - and in which is never immediately followed by , is never immediately followed by , and is never immediately followed by . How many seven-letter good words are there?
There are three letters to make the first letter in the sequence. However, after the first letter (whatever it is), only two letters can follow it, since one of the letters is restricted. Therefore, the number of seven-letter good words is
Therefore, there are seven-letter good words.
There are three choices for the first letter and two choices for each subsequent letter, so there are -letter good words. Substitute to find there are seven-letter good words. ~ aopsav (Credit to AoPS Alcumus)
Solution 3 (Recursion)
We solve this problem using recursion. Let f(x) be the number of x-letter good words. Thus f(1) = 3 (A, B or C) and the answer is just f(7). The recurrence relation can be found by considering the last letter of one of the valid strings of length x - 1. There are 2 possibilities for the next letter and thus f(x) = 2 * f(x-1). Now we can find a closed form as f(x) = 3 * 2 ^ (x - 1) (easy to prove by induction) and thus f(7) = 64 * 3 = seven-letter good words. ~AK2006
|2003 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|