Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 5"
m |
Mathgeek2006 (talk | contribs) m (→Solution 1 (recursive)) |
||
| Line 11: | Line 11: | ||
Using those three recursive rules, and that <math>a_2 = 4, b_2 = 2, c_2=2</math>, we can make a table: | Using those three recursive rules, and that <math>a_2 = 4, b_2 = 2, c_2=2</math>, we can make a table: | ||
<cmath> | <cmath> | ||
| − | \begin{ | + | \begin{array}{|r||r|r|r|} |
\hline | \hline | ||
&a_n&b_n&c_n \\ | &a_n&b_n&c_n \\ | ||
| Line 25: | Line 25: | ||
10 & 472 & 648 & 816 \\ | 10 & 472 & 648 & 816 \\ | ||
\hline | \hline | ||
| − | \end{ | + | \end{array} |
</cmath> | </cmath> | ||
For simplicity, we used <math>\mod 1000</math>. Thus, the answer is <math>a_{10} + b_{10} + c_{10} \equiv \boxed{936} \pmod{1000}</math>. (the real answer is <math>15936</math>.) | For simplicity, we used <math>\mod 1000</math>. Thus, the answer is <math>a_{10} + b_{10} + c_{10} \equiv \boxed{936} \pmod{1000}</math>. (the real answer is <math>15936</math>.) | ||
Revision as of 18:24, 10 March 2015
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,
.
with CC at the end by appending a constant (
) to the end of a word of length 
, as there are two possible constants we can append.
characters of each other. Thus, 
.
.Using those three recursive rules, and that 
, we can make a table:
![\[\begin{array}{|r||r|r|r|} \hline &a_n&b_n&c_n \\ \hline 2 & 4 & 2 & 2 \\ 3 & 12 & 4 & 4 \\ 4 & 32 & 12 & 8 \\ 5 & 80 & 32 & 24 \\ 6 & 208 & 80 & 64 \\ 7 & 544 & 208 & 160 \\ 8 & 408 & 544 & 416 \\ 9 & 648 & 408 & 88 \\ 10 & 472 & 648 & 816 \\ \hline \end{array}\]](http://latex.artofproblemsolving.com/0/3/a/03a5bbbc5b7fa2270e87aa55afd8203516d68f5e.png)
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 | ||
