Difference between revisions of "University of South Carolina High School Math Contest/1993 Exam/Problem 11"
Dylanpshen (talk | contribs) m (→Solution 2: Made derangements link article work) |
|||
| (8 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
== Problem == | == 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? | ||
| − | <center><math> \mathrm{(A) \ } \qquad \mathrm{(B) \ } \qquad \mathrm{(C) \ } \qquad \mathrm{(D) \ } \qquad \mathrm{(E) \ } </math></center> | + | <center><math> \mathrm{(A) \ } 1/3 \qquad \mathrm{(B) \ }3/8 \qquad \mathrm{(C) \ }5/12 \qquad \mathrm{(D) \ } 1/2 \qquad \mathrm{(E) \ }9/16 </math></center> |
== Solution == | == Solution == | ||
| + | This is the number of [[derangement]]s 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 <math>3(1\cdot1 + 2 \cdot 1) = 9</math> good arrangements. (Equivalently, one could say that the only [[permutation]]s of 4 objects with no fixed points are those with [[cycle notation]] <math>(abcd)</math> and <math>(ab)(cd)</math>, of which there are 6 and 3, respectively.) Thus the probability is <math>\frac{9}{4!} = \frac 38 \Longrightarrow \mathrm{(B)}</math>. |
| − | * [[University of South Carolina High School Math Contest/1993 Exam]] | + | |
| + | Counting the complement: | ||
| + | |||
| + | ---- | ||
| + | ==Solution 2== | ||
| + | Using the formula for [[derangement]]s, <math>!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.</math>, we can substitute in our values to find that the number of derangements is <math>24\cdot (\frac{1}{1}-\frac{1}{1}+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}).</math> Therefore, the number of derangements is 9. The probability of getting a derangement is <math>\frac{9}{24}</math> Simplifying, we get <math>\frac 38 \Longrightarrow \mathrm{(B)}</math>. | ||
| + | * [[University of South Carolina High School Math Contest/1993 Exam/Problem 10|Previous Problem]] | ||
| + | * [[University of South Carolina High School Math Contest/1993 Exam/Problem 12|Next Problem]] | ||
| + | * [[University of South Carolina High School Math Contest/1993 Exam|Back to Exam]] | ||
| + | |||
| + | [[Category:Introductory Combinatorics Problems]] | ||
Latest revision as of 16:27, 25 October 2023
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?
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 
good arrangements. (Equivalently, one could say that the only permutations of 4 objects with no fixed points are those with cycle notation 
and 
, of which there are 6 and 3, respectively.) Thus the probability is 
.
Counting the complement:
Solution 2
Using the formula for derangements, 
, we can substitute in our values to find that the number of derangements is 
Therefore, the number of derangements is 9. The probability of getting a derangement is 
Simplifying, we get 
.
