Difference between revisions of "University of South Carolina High School Math Contest/1993 Exam/Problem 14"
(→Solution) |
|||
(2 intermediate revisions by one other user not shown) | |||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
+ | How many permutations of 1, 2, 3, 4, 5, 6, 7, 8, 9 have: | ||
+ | * 1 appearing somewhere to the left of 2, | ||
+ | * 3 somewhere to the left of 4, and | ||
+ | * 5 somewhere to the left of 6? | ||
+ | For example, 8 1 5 7 2 3 9 4 6 would be such a permutation. | ||
− | <center><math> \mathrm{(A) \ } \qquad \mathrm{(B) \ } \qquad \mathrm{(C) \ } \qquad \mathrm{(D) \ } \qquad \mathrm{(E) \ } </math></center> | + | <center><math> \mathrm{(A) \ }9\cdot 7! \qquad \mathrm{(B) \ } 8! \qquad \mathrm{(C) \ }5!4! \qquad \mathrm{(D) \ }8!4! \qquad \mathrm{(E) \ }8!+6!+4! </math></center> |
== Solution == | == Solution == | ||
+ | There are <math>9!</math> (the [[factorial]] of 9) total [[permutation]]s of the [[element]]s of that [[set]]. 1 is to the left of 2 in exactly half of these. 3 is also to the left of 4 in exactly half of the permutations, and 5 is to the left of 6 in exactly half of the permutations. These three events are totally independent of each other, so the number we want to calculate is <math>\frac12\cdot\frac12\cdot\frac12\cdot9! = \frac18\cdot9\cdot8\cdot7! = 9\cdot7!</math> which is answer choice <math>\mathrm{(A)}</math>. | ||
− | == | + | Alternatively, note that we can choose <math>{9\choose 2}</math> places for the 1 and 2, then <math>{7\choose2}</math> places for the 3 and 4, then <math>5\choose 2</math> places for the 5 and 6, and the arrange the 7, 8 and 9 in <math>3!</math> ways, giving us a total of <math>{9\choose2}\cdot{7\choose2}\cdot{5\choose2}\cdot3! = \frac{(9\cdot8)\cdot(7\cdot6)\cdot(5\cdot4)\cdot3!}{2\cdot2\cdot2} = 9\cdot7! \Longrightarrow \mathrm{(A)}</math>. |
− | * [[University of South Carolina High School Math Contest/1993 Exam]] | + | |
+ | ---- | ||
+ | |||
+ | * [[University of South Carolina High School Math Contest/1993 Exam/Problem 13|Previous Problem]] | ||
+ | * [[University of South Carolina High School Math Contest/1993 Exam/Problem 15|Next Problem]] | ||
+ | * [[University of South Carolina High School Math Contest/1993 Exam|Back to Exam]] | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] |
Latest revision as of 16:54, 17 August 2006
Problem
How many permutations of 1, 2, 3, 4, 5, 6, 7, 8, 9 have:
- 1 appearing somewhere to the left of 2,
- 3 somewhere to the left of 4, and
- 5 somewhere to the left of 6?
For example, 8 1 5 7 2 3 9 4 6 would be such a permutation.
Solution
There are (the factorial of 9) total permutations of the elements of that set. 1 is to the left of 2 in exactly half of these. 3 is also to the left of 4 in exactly half of the permutations, and 5 is to the left of 6 in exactly half of the permutations. These three events are totally independent of each other, so the number we want to calculate is which is answer choice .
Alternatively, note that we can choose places for the 1 and 2, then places for the 3 and 4, then places for the 5 and 6, and the arrange the 7, 8 and 9 in ways, giving us a total of .