Mock AIME 1 Pre 2005 Problems/Problem 7

Problem

Let $N$ denote the number of permutations of the $15$ -character string AAAABBBBBCCCCCC such that

None of the first four letter is an A.
None of the next five letters is a B.
None of the last six letters is a C.

Find the remainder when $N$ is divided by $1000$ .

Solution

Let there be $k$ iAs amongst the five numbers in the middle (those mentioned in condition ii). There are $4-k$ As amongst the last six numbers then. Also, there are $5-k$ Cs amongst the middle five numbers, and so there are $6-(5-k) = k+1$ Cs amongst the first four numbers.

Thus, there are ${4 \choose k+1}$ ways to arrange the first four numbers, ${5 \choose k}$ ways to arrange the middle five numbers, and ${6 \choose 4-k} = {6\choose k+2}$ ways to arrange the last six numbers. Notice that $k=4$ 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$ And $N \equiv \boxed{320} \pmod{1000}$ .

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

Page

Toolbox

Search

Mock AIME 1 Pre 2005 Problems/Problem 7

Problem

Solution

See also