Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 5"
(→Solution 3) |
(→Solution 3) |
||
Line 58: | Line 58: | ||
Case <math>3</math>: The word contains <math>2</math> <math>O</math>s. | 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>s. | ||
+ | |||
+ | This is equivalent to inserting <math>1</math> <math>O</math> into | ||
+ | <math></math>C,C,C,C,C,C,C,C,C$ | ||
+ | Which has 10 possibilities. | ||
==See Also== | ==See Also== |
Revision as of 10:28, 28 November 2019
Problem
In Zuminglish, all words consist only of the letters and
. As in English,
is said to be a vowel and
and
are consonants. A string of
and
is a word in Zuminglish if and only if between any two
there appear at least two consonants. Let
denote the number of
-letter Zuminglish words. Determine the remainder obtained when
is divided by
.
Contents
Solution
Solution 1 (recursive)
Let denote the number of
-letter words ending in two constants (CC),
denote the number of
-letter words ending in a constant followed by a vowel (CV), and let
denote the number of
-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
with CC at the end by appending a constant (
) to the end of a word of length
that ends in a constant. Thus, we have the recursion
, as there are two possible constants we can append.
- We can only form a word of length
with a CV by appending
to the end of a word of length
that ends with CC. This is because we cannot append a vowel to VC, otherwise we'd have two vowels within
characters of each other. Thus,
.
- We can only form a word of length
with a VC by appending a constant to the end of a word of length
that ends with CV. Thus,
.
Using those three recursive rules, and that , we can make a table:
For simplicity, we used
. Thus, the answer is
. (the real answer is
.)
Solution 2 (combinatorics)
See solutions pdf.
Solution 3
Let denotes vowel and
denotes consonants. Notice that there can be a maximum of 4
s. Specifically,
Doing simple casework:
Case : The word contains
vowels.
For each , there are
choices. There is a total of
possible words.
Case : The word contains
vowels.
Consider the word
We want to incorporate
s into the
intervals.
If the s are in
separate intervals, there are
possibilities.
If the s are in
different intervals, then one has
s and the other has
. There are
possibilities.
If the s are in the same intervals, there are
possibilities.
In total, case holds
possible words.
Case : The word contains
s.
This is equivalent to inserting
s into the word
There are
possibilities in total.
There possibilities when the
s have no
s in between them.
There possibilities when the
s have
in between them.
In total, case holds
possible words.
Case : The word contains
s.
This is equivalent to inserting
into
$$ (Error compiling LaTeX. Unknown error_msg)C,C,C,C,C,C,C,C,C$
Which has 10 possibilities.
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 |