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

(Solution 3)
(Solution 2 (combinatorics))
(11 intermediate revisions by one other user not shown)
Line 32: Line 32:
 
See [http://www.tjhsst.edu/~tmildorf/math/PracticeAIME3Solutions.pdf solutions pdf].
 
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 ===
 
=== 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 <math>2</math> <math>O</math>s into the word
 +
<cmath>C,C,C,C,C,C,C,C</cmath>
 +
There are <math>\frac{9\cdot8}{2}=36</math> possibilities in total.
 +
 +
There <math>8</math> possibilities when the <math>2</math> <math>O</math>s have no <math>C</math>s in between them.
 +
 +
There <math>7</math> possibilities when the <math>2</math> <math>O</math>s have <math>1</math> <math>C</math> in between them.
 +
 +
In total, case <math>3</math> holds <math>(36-7-8)\cdot2^8=7936</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
  
 
==See Also==
 
==See Also==

Revision as of 23:52, 9 June 2020

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 $2$ $O$s into the word \[C,C,C,C,C,C,C,C\] There are $\frac{9\cdot8}{2}=36$ possibilities in total.

There $8$ possibilities when the $2$ $O$s have no $C$s in between them.

There $7$ possibilities when the $2$ $O$s have $1$ $C$ in between them.

In total, case $3$ holds $(36-7-8)\cdot2^8=7936$ 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

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