Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 5"
(recursive solution)
Line 2: Line 2:
 
In Zuminglish, all words consist only of the letters <math>M, O,</math> and <math>P</math>. As in English, <math>O</math> is said to be a vowel and <math>M</math> and <math>P</math> are consonants. A string of <math>M's, O's,</math> and <math>P's</math> is a word in Zuminglish if and only if between any two <math>O's</math> there appear at least two consonants. Let <math>N</math> denote the number of <math>10</math>-letter Zuminglish words. Determine the remainder obtained when <math>N</math> is divided by <math>1000</math>.
 
In Zuminglish, all words consist only of the letters <math>M, O,</math> and <math>P</math>. As in English, <math>O</math> is said to be a vowel and <math>M</math> and <math>P</math> are consonants. A string of <math>M's, O's,</math> and <math>P's</math> is a word in Zuminglish if and only if between any two <math>O's</math> there appear at least two consonants. Let <math>N</math> denote the number of <math>10</math>-letter Zuminglish words. Determine the remainder obtained when <math>N</math> is divided by <math>1000</math>.
  
 +
__TOC__
 
==Solution==
 
==Solution==
−
{{solution}}
+
=== Solution 1 (recursive) ===
 +
Let <math>a_n</math> denote the number of <math>n</math>-letter words ending in two constants (<tt>CC</tt>), <math>b_n</math> denote the number of <math>n</math>-letter words ending in a constant followed by a vowel (<tt>CV</tt>), and let <math>c_n</math> denote the number of <math>n</math>-letter words ending in a vowel followed by a constant (<tt>VC</tt> - the only other combination, two vowels, is impossible due to the problem statement). Then, note that:
 +
*We can only form a word of length <math>n+1</math> with <tt>CC</tt> at the end by appending a constant (<math>M,P</math>) to the end of a word of length <math>n</math> that ends in a constant. Thus, we have the [[recursion]] <math>a_{n+1} = 2(a_n + c_n)</math>, as there are two possible constants we can append.
 +
*We can only form a word of length <math>n+1</math> with a <tt>CV</tt> by appending <math>O</math> to the end of a word of length <math>n</math> that ends with <tt>CC</tt>. This is because we cannot append a vowel to <tt>VC</tt>, otherwise we'd have two vowels within <math>2</math> characters of each other. Thus, <math>b_{n+1} = a_n</math>.
 +
*We can only form a word of length <math>n+1</math> with a <tt>VC</tt> by appending a constant to the end of a word of length <math>n</math> that ends with <tt>CV</tt>. Thus, <math>c_{n+1} = 2b_n</math>.
 +
Using those three recursive rules, and that <math>a_2 = 4, b_2 = 2, c_2=2</math>, we can make a table:
 +
<cmath>
 +
\begin{tabular}{|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{tabular}
 +
</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>.)
 +
 
 +
=== Solution 2 (combinatorics) ===
 +
See [http://www.tjhsst.edu/~tmildorf/math/PracticeAIME3Solutions.pdf solutions pdf].
  
 
==See also==
 
==See also==
 +
{{Mock AIME box|year=Pre 2005|n=3|num-b=4|num-a=6|t=18963}}
 +
 +
[[Category:Intermediate Algebra Problems]]

Revision as of 21:45, 19 June 2008

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{tabular}{|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{tabular}\] (Error compiling LaTeX. Unknown error_msg)

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_3_Pre_2005_Problems/Problem_5&oldid=26706"