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

Latest revision as of 15:03, 17 October 2021

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.

This site does not exist. Please post your solution here on the AOPS solution page.

Solution 3

Let $O$ denotes vowel and $C$ denotes consonants. Notice that there can be a maximum of 4 $O$ s. Specifically, $O,C,C,O,C,C,O,C,C,O$ Doing simple casework:

Case $1$ : The word contains $4$ vowels.

For each $C$ , there are $2$ choices. There is a total of $2^6=64$ possible words.

Case $2$ : The word contains $3$ vowels.

Consider the word $O,C,C,O,C,C,O$ We want to incorporate $3$ $C$ s into the $4$ intervals.

If the $C$ s are in $3$ separate intervals, there are ${4\choose3}=4$ possibilities.

If the $C$ s are in $2$ different intervals, then one has $2$ $C$ s and the other has $1$ $C$ . There are $2\cdot{4\choose2}=12$ possibilities.

If the $C$ s are in the same intervals, there are $4$ possibilities.

In total, case $2$ holds $(4+12+4)\cdot2^7=2560$ possible words.

Case $3$ : The word contains $2$ $O$ s.

This is equivalent to inserting 6 C's into OCCO. There are 3 spots: before the first O, in between the 2 O's, and behind the last O. Stars and bars with insertion (allowing 0) tells us there are ${6+3-1 \choose 3-1}=28$ possibilities. In total, case 3 holds $28 \cdot 2^8 = 7168$ possible words.

Case $4$ : The word contains $1$ $O$ .

This is equivalent to inserting $1$ $O$ into $C,C,C,C,C,C,C,C,C$ Which has $10\cdot2^9=5120$ possibilities.

Case $5$ : The word contains no $O$ s.

There are $2^{10}=1024$ possible words.

Adding up the 5 cases yields $N=15936$ .

Thus $N\equiv \boxed{936}\mod 1000$ .

~ Nafer, Edited by Tom

@@ Line 1: / Line 1: @@
-<math>5.</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>.
+==Problem==
+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 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{array}{|r||r|r|r|}
+\hline
+&a_n&b_n&c_n \\
+\hline
+& 4 & 2 & 2 \\
+& 12 & 4 & 4 \\
+& 32 & 12 & 8 \\
+& 80 & 32 & 24 \\
+& 208 & 80 & 64 \\
+& 544 & 208 & 160 \\
+& 408 & 544 & 416 \\
+& 648 & 408 & 88 \\
+& 472 & 648 & 816 \\
+\hline
+\end{array}
+</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].
+*This site does not exist. Please post your solution here on the AOPS solution page.
+=== Solution 3 ===
+Let <math>O</math> denotes vowel and <math>C</math> denotes consonants. Notice that there can be a maximum of 4 <math>O</math>s. Specifically,
+<cmath>O,C,C,O,C,C,O,C,C,O</cmath>
+Doing simple casework:
+Case <math>1</math>: The word contains <math>4</math> vowels.
+For each <math>C</math>, there are <math>2</math> choices. There is a total of <math>2^6=64</math> possible words.
+Case <math>2</math>: The word contains <math>3</math> vowels.
+Consider the word
+<cmath>O,C,C,O,C,C,O</cmath>
+We want to incorporate <math>3</math> <math>C</math>s into the <math>4</math> intervals.
+If the <math>C</math>s are in <math>3</math> separate intervals, there are <math>{4\choose3}=4</math> possibilities.
+If the <math>C</math>s are in <math>2</math> different intervals, then one has <math>2</math> <math>C</math>s and the other has <math>1</math> <math>C</math>. There are <math>2\cdot{4\choose2}=12</math> possibilities.
+If the <math>C</math>s are in the same intervals, there are <math>4</math> possibilities.
+In total, case <math>2</math> holds <math>(4+12+4)\cdot2^7=2560</math> possible words.
+Case <math>3</math>: The word contains <math>2</math> <math>O</math>s.
+This is equivalent to inserting 6 C's into OCCO. There are 3 spots: before the first O, in between the 2 O's, and behind the last O.
+Stars and bars with insertion (allowing 0) tells us there are <math>{6+3-1 \choose 3-1}=28</math> possibilities. In total, case 3 holds <math>28 \cdot 2^8 = 7168</math> possible words.
+Case <math>4</math>: The word contains <math>1</math> <math>O</math>.
+This is equivalent to inserting <math>1</math> <math>O</math> into
+<cmath>C,C,C,C,C,C,C,C,C</cmath>
+Which has <math>10\cdot2^9=5120</math> possibilities.
+Case <math>5</math>: The word contains no <math>O</math>s.
+There are <math>2^{10}=1024</math> possible words.
+Adding up the 5 cases yields <math>N=15936</math>.
+Thus <math>N\equiv \boxed{936}\mod 1000</math>.
+~ Nafer, Edited by Tom
+==See Also==
+{{Mock AIME box|year=Pre 2005|n=3|num-b=4|num-a=6|t=18963}}
+[[Category:Intermediate Algebra Problems]]

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

Page

Toolbox

Search