1
$\begingroup$

Four friends, Adin, Brigid, Chioma, and Draven, go to a restaurant and each order a different dish. The waiter took down the order but forgot to mark for whom each dish was for, and hence served a random dish to each of the four patrons. What is the probability that none of the customers got the dish they ordered? Enter your answer as a fraction reduced to simplest terms.

Let us intentionally give the people the wrong dish. Suppose Adin ordered A, Brigid ordered B, Chioma ordered C, Draven ordered D.

We have three choices to give Aidan (B,C,D). We give Aidan an element of $(B,C,D)=z_1$

We have two choices to give Brigid $(A,C,D)\smallsetminus z_1$. We give Brigid $z_2$

We have two choices to give Chioma $(B,D,A)\smallsetminus z_2$ We give Chioma $z_3$.

We have one choice to give Draven.

Why is the final answer $\dfrac{3}{8}$ and not $\dfrac{1}{2}=\dfrac{3 \cdot 2^2}{24}$?

$\endgroup$
2

1 Answer 1

Reset to default
3
$\begingroup$

The reason becomes clear when you explicitly enumerate these outcomes.

Let $(z_1, z_2, z_3, z_4)$ where $z_i \in \{A, B, C, D\}$ for $i = 1, 2, 3, 4$ be an ordered quadruplet that denotes the dish given to Adin, Brigid, Chioma, and Draven respectively. Then one outcome might be $(B, C, D, A)$, in which no one got their own dish. You can also see that in this outcome, the choices for Brigid were in fact among $\{A, C, D\}$, not two choices. And although Chioma seemingly has two choices $\{A, D\}$, the choice $A$ is not allowed, because this would force Draven to receive $D$. So Chioma actually has only one choice, $D$, or else it is not possible to prevent a match.

Clearly, a more sophisticated accounting of the dependence of subsequent choices based on the previous dish assignments is needed. And this is why your enumeration does not work. If you were to explicitly write out all derangements, they would be:

$$(B,A,D,C) \\ (B,C,D,A) \\ (B,D,A,C) \\ (C,A,D,B) \\ (C,D,A,B) \\ (C,D,B,A) \\ (D,A,B,C) \\ (D,C,A,B) \\ (D,C,B,A) $$ And there are only $9$ of these, out of $4! = 24$ possible arrangements, for a probability of $3/8$ as claimed.

To count these in the general case, the usual approach is to use a principle called "inclusion-exclusion." See also the article for derangements.

$\endgroup$

You must log in to answer this question.