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

University of South Carolina High School Math Contest/1993 Exam/Problem 11

Revision as of 10:07, 13 February 2018 by Ishi123 (talk | contribs) (→‎Solution)

Problem

Suppose that 4 cards labeled 1 to 4 are placed randomly into 4 boxes also labeled 1 to 4, one card per box. What is the probability that no card gets placed into a box having the same label as the card?

$\mathrm{(A) \ } 1/3 \qquad \mathrm{(B) \ }3/8 \qquad \mathrm{(C) \ }5/12 \qquad \mathrm{(D) \ } 1/2 \qquad \mathrm{(E) \ }9/16$

Solution

This is the number of derangements of 4 objects. We can know the formula for derangements or count in one of two ways:

Counting directly: The card labeled 1 has 3 places to go. Without loss of generality we may say that it goes in the place marked 2. Now, if card 2 goes into box 1, we have only one possibility because cards 3 and 4 must be interchanged. Otherwise, there are 2 possibilities for card 2, and each of these leads to one more possible arrangement (if card 2 goes in box 3, card 3 must go in box 4 and card 4 in box 1, while if card 2 goes in box 4, card 4 must go in box 3, and card 3 must go in box 1). This gives us a total of $3(1\cdot1 + 2 \cdot 1) = 9$ good arrangements. (Equivalently, one could say that the only permutations of 4 objects with no fixed points are those with cycle notation $(abcd)$ and $(ab)(cd)$, of which there are 6 and 3, respectively.) Thus the probability is $\frac{9}{4!} = \frac 38 \Longrightarrow \mathrm{(B)}$.

Counting the complement:

Solution 2

Using the formula for derangements, $!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.$, we can substitute in our values to find that the number of derangements is $24\cdot\frac{1}{1}-\frac{1}{1}+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}.$ Therefore, the number of derangements is 9. The probability of getting a derangement is $\frac{9}{24}$ Simplifying, we get $\frac 38 \Longrightarrow \mathrm{(B)}$.

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