Difference between revisions of "University of South Carolina High School Math Contest/1993 Exam/Problem 11"
m (→Solution) |
(→Solution) |
||
Line 5: | Line 5: | ||
== Solution == | == Solution == | ||
− | The probability is <math>\frac{ | + | 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>. | ||
+ | |||
+ | Counting the complement: | ||
− | |||
---- | ---- | ||
Revision as of 20:33, 20 August 2006
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: