Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 1 Pre 2005 Problems/Problem 7"

(problem/solution)
 
m (→‎Solution: typo fix)
Line 9: Line 9:
  
 
== Solution ==
 
== Solution ==
−
Let there be <math>k</math> i<tt>A</tt>s amongst the five numbers in the middle (those mentioned in condition ii). 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.
+
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

Revision as of 19:11, 21 March 2008

Problem

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

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

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

Solution

Let there be $k$ As amongst the five numbers in the middle (those mentioned in condition [2]). 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}$.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_1_Pre_2005_Problems/Problem_7&oldid=24197"