Mock AIME 3 Pre 2005 Problems/Problem 5
Problem
In Zuminglish, all words consist only of the letters and . As in English, is said to be a vowel and and are consonants. A string of and is a word in Zuminglish if and only if between any two there appear at least two consonants. Let denote the number of -letter Zuminglish words. Determine the remainder obtained when is divided by .
Solution
Solution 1 (recursive)
Let denote the number of -letter words ending in two constants (CC), denote the number of -letter words ending in a constant followed by a vowel (CV), and let denote the number of -letter words ending in a vowel followed by a constant (VC - the only other combination, two vowels, is impossible due to the problem statement). Then, note that:
- We can only form a word of length with CC at the end by appending a constant () to the end of a word of length that ends in a constant. Thus, we have the recursion , as there are two possible constants we can append.
- We can only form a word of length with a CV by appending to the end of a word of length that ends with CC. This is because we cannot append a vowel to VC, otherwise we'd have two vowels within characters of each other. Thus, .
- We can only form a word of length with a VC by appending a constant to the end of a word of length that ends with CV. Thus, .
Using those three recursive rules, and that , we can make a table: For simplicity, we used . Thus, the answer is . (the real answer is .)
Solution 2 (combinatorics)
See solutions pdf.
See Also
Mock AIME 3 Pre 2005 (Problems, Source) | ||
Preceded by Problem 4 |
Followed by Problem 6 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 |