Determine the probability that no guest will receive the proper hat.

Question

Suppose that 4 guests check their hats when they arrive at a restaurant, and that these hats are returned to them in a random order when they leave. Determine the probability that no guest will receive the proper hat.

My attempt: So I know that there are 4! ways of "arranging" the hats. The probability of each receiving their hat is 1/4 and the probability that they will not receive the right hat is 3/4.

I think the answer should be something like:

$\frac{}{4!}$

where the 4! is from the total ways of arranging the hats, and the numerator is the number of "correct" ways to arrange the hats (so no one gets their own hat)But I can't seem to think of how to express that mathematically.

How should I think about this problem instead?

So the book gives the answer 3/8 and myclassmate said the answer is

$\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}=\frac{3}{8}$

But I don't understand why this is?

Answer 1

Use inclusion-exclusion theorem/formula/principle. Total number of ways to distribute 4 hats amon 4 people is $4!$. Now subtract the number of ways 1 person leaves with his hat, add two people left with their hats, subtract three people left with their hats, add 4 ppl left with their hats (the last one is obviously 1).

Answer 2

Sorry for the very late reply, lmao. Anyhow, the answer is to use derangements: an arrangement such that no elements appear in their original position. Basically, if you map a hat and its owner, you can find an arrangement such that no hat is mapped to its original owner again, which is just derangement. It is also useful to know when the question asked it "If at least one person leave with their original hats", that would just be the complement of the derangement and be (1 - Pr(x)), where x is the probability that no one leaves with their hats.

Using derangement, you can see that 9 arrangements fit the category and since there's 4! available permutation, the result is 9/24 = 3/8

Answer 3

Pr

n i=1 Ai

= n i=1 Pr(Ai) −

i<j Pr(Ai ∩ Aj ) +

i<j<k Pr(Ai ∩ Aj ∩ Ak) −

i<j<k<l Pr(Ai ∩ Aj ∩ Ak ∩ Al) + . . .

• (−1)n+1 Pr(A1 ∩ A2 ∩ . . . ∩ An). We'll use this probability union formula for the solution. Let's assume that a first man will recieve a proper hat and the probability for this event is P(A1) = 1/n and as there are 4 cases like thet the sum is n*(1/n)=1

2. Then the probability that first or second men will receive proper hat is P(A1 or A2)=1/n*(n-1) and as there are Cn,2 ways to place these two men the sum will be Cn,21(n(n-1))
3. Then the probability that any three men will receive a proper hat will be P(A1 or A2 or A3) = 1/n(n-1)(n-2) and the sum will be Cn,3*1/n(n-1)(n-2)
4. The sum P(A1 or A2 or A3 or A4) = 1/n! Let's compute: 1 - 1/2! + 1/3! - 1/4! = 15/24 This is when each man will receive a proper hat and the probability that no man will receive a proper hat is 1-15/24 = 9/24 = 3/8