Difference between revisions of "Mock AIME 1 Pre 2005 Problems/Problem 7"
(problem/solution) |
(→Problem) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Let <math>N</math> denote the number of permutations of the <math>15</math>-character string < | + | Let <math>N</math> denote the number of permutations of the <math>15</math>-character string <math>AAAABBBBBCCCCCC</math> such that |
| − | # None of the first four | + | # None of the first four letters is an <math>A</math>. |
| − | # None of the next five letters is a < | + | # None of the next five letters is a <math>B</math>. |
| − | # None of the last six letters is a < | + | # None of the last six letters is a <math>C</math>. |
Find the remainder when <math>N</math> is divided by <math>1000</math>. | Find the remainder when <math>N</math> is divided by <math>1000</math>. | ||
== Solution == | == Solution == | ||
| − | Let there be <math>k</math> | + | Let there be <math>k</math> <tt>A</tt>s amongst the five numbers in the middle (those mentioned in condition [2]). There are <math>4-k</math> <tt>A</tt>s amongst the last six numbers then. Also, there are <math>5-k</math> <tt>C</tt>s amongst the middle five numbers, and so there are <math>6-(5-k) = k+1</math> <tt>C</tt>s amongst the first four numbers. |
Thus, there are <math>{4 \choose k+1}</math> ways to arrange the first four numbers, <math>{5 \choose k}</math> ways to arrange the middle five numbers, and <math>{6 \choose 4-k} = {6\choose k+2}</math> ways to arrange the last six numbers. Notice that <math>k=4</math> leads to a contradiction, so the desired sum is | Thus, there are <math>{4 \choose k+1}</math> ways to arrange the first four numbers, <math>{5 \choose k}</math> ways to arrange the middle five numbers, and <math>{6 \choose 4-k} = {6\choose k+2}</math> ways to arrange the last six numbers. Notice that <math>k=4</math> leads to a contradiction, so the desired sum is | ||
Latest revision as of 16:27, 23 February 2013
Problem
Let 
denote the number of permutations of the 
-character string 
such that
- None of the first four letters is an
. - None of the next five letters is a
. - None of the last six letters is a
.
.
.
.Find the remainder when is divided by 
.
Solution
Let there be 
As amongst the five numbers in the middle (those mentioned in condition [2]). There are 
As amongst the last six numbers then. Also, there are 
Cs amongst the middle five numbers, and so there are 
Cs amongst the first four numbers.
Thus, there are 
ways to arrange the first four numbers, 
ways to arrange the middle five numbers, and 
ways to arrange the last six numbers. Notice that 
leads to a contradiction, so the desired sum is
![\[\sum_{k=0}^{3} {4\choose k+1}{5\choose k}{6\choose k+2} = 60 + 600 + 600 + 60 = 1320\]](http://latex.artofproblemsolving.com/d/2/e/d2ef4917e8074dec225338b01302fd130a1583a8.png)
And 
.
See also
| Mock AIME 1 Pre 2005 (Problems, Source) | ||
| Preceded by Problem 6 |
Followed by Problem 8 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
