Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 5"

m
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{tabular}{|r||r|r|r|}
+
\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{tabular}
+
\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 19:24, 10 March 2015

Problem

In Zuminglish, all words consist only of the letters $M, O,$ and $P$. As in English, $O$ is said to be a vowel and $M$ and $P$ are consonants. A string of $M's, O's,$ and $P's$ is a word in Zuminglish if and only if between any two $O's$ there appear at least two consonants. Let $N$ denote the number of $10$-letter Zuminglish words. Determine the remainder obtained when $N$ is divided by $1000$.

Solution

Solution 1 (recursive)

Let $a_n$ denote the number of $n$-letter words ending in two constants (CC), $b_n$ denote the number of $n$-letter words ending in a constant followed by a vowel (CV), and let $c_n$ denote the number of $n$-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 $n+1$ with CC at the end by appending a constant ($M,P$) to the end of a word of length $n$ that ends in a constant. Thus, we have the recursion $a_{n+1} = 2(a_n + c_n)$, as there are two possible constants we can append.
  • We can only form a word of length $n+1$ with a CV by appending $O$ to the end of a word of length $n$ that ends with CC. This is because we cannot append a vowel to VC, otherwise we'd have two vowels within $2$ characters of each other. Thus, $b_{n+1} = a_n$.
  • We can only form a word of length $n+1$ with a VC by appending a constant to the end of a word of length $n$ that ends with CV. Thus, $c_{n+1} = 2b_n$.

Using those three recursive rules, and that $a_2 = 4, b_2 = 2, c_2=2$, 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}\] For simplicity, we used $\mod 1000$. Thus, the answer is $a_{10} + b_{10} + c_{10} \equiv \boxed{936} \pmod{1000}$. (the real answer is $15936$.)

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
Invalid username
Login to AoPS