Mock AIME 3 Pre 2005 Problems/Problem 5

From AoPSWiki

(Redirected from Mock AIME 3 Pre 2005/Problem 5)

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 \\\hline2 & 4 & 2 & 2 \\3 & 12 & 4 & 4 \\4 ...$ 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.

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

Personal tools

Navigation

Search

Toolbox