Difference between revisions of "Mock AIME 3 Pre 2005 Problems/Problem 5"
(→Solution 3) |
Tomqiu2023 (talk | contribs) (→Solution 3) |
||
(9 intermediate revisions by 3 users 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 === | ||
Line 59: | Line 60: | ||
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 | + | 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>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | 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 | This is equivalent to inserting <math>1</math> <math>O</math> into | ||
Line 77: | Line 71: | ||
Case <math>5</math>: The word contains no <math>O</math>s. | Case <math>5</math>: The word contains no <math>O</math>s. | ||
− | There are <math>2^10=1024</math> possible words. | + | 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== | ==See Also== |
Latest revision as of 15:03, 17 October 2021
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.
- This site does not exist. Please post your solution here on the AOPS solution page.
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 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 possibilities. In total, case 3 holds possible words.
Case : The word contains .
This is equivalent to inserting into Which has possibilities.
Case : The word contains no s.
There are possible words.
Adding up the 5 cases yields .
Thus .
~ Nafer, Edited by Tom
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 |