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 "University of South Carolina High School Math Contest/1993 Exam/Problem 14"
(→‎Solution)
 
Line 9: Line 9:
  
 
== Solution ==
 
== Solution ==
−
For the nine slots, we have to choose two spots for each of our pairs <math>(1,2), (3,4), (5,6)</math>. There are <math>{9\choose 2}{7\choose 2}{5\choose 2}</math> ways to do this, but we must multiply this by <math>3!</math> because there are three different pairs that we can choose in different "orders" for the <math>{9\choose 2}, {7\choose 2}, {5\choose 2}</math>. We also need to multiply by <math>3!</math> again for the remaining three slots for <math>7,8,9</math>. Thus the total number of ways is <math>3!{9\choose 2}{7\choose 2}{5\choose 2}3!</math>, which after simplifying is choice <math>(a)</math>.
+
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>.
  
 
----
 
----

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.

$\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!$

Solution

There are $9!$ (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 $\frac12\cdot\frac12\cdot\frac12\cdot9! = \frac18\cdot9\cdot8\cdot7! = 9\cdot7!$ which is answer choice $\mathrm{(A)}$.

Alternatively, note that we can choose ${9\choose 2}$ places for the 1 and 2, then ${7\choose2}$ places for the 3 and 4, then $5\choose 2$ places for the 5 and 6, and the arrange the 7, 8 and 9 in $3!$ ways, giving us a total of ${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)}$.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=University_of_South_Carolina_High_School_Math_Contest/1993_Exam/Problem_14&oldid=9630"