WordGPT

The hat-check problem for 4 people

Exercise · Level 4 (Hard)

Four people leave their hats at the door and get them back at random. What is the probability that nobody gets their own hat?

!4/4!= ?!4/4!=\ ?

wordgptpro.com

Solution

  1. There are 4!=244!=24 ways to return the hats. Inclusion–exclusion on 'someone gets their own hat':

    !4=4!−(41)3!+(42)2!−(43)1!+(44)0!=24−24+12−4+1=9\begin{aligned}&!4\\&=4!-\binom41 3!+\binom42 2!-\binom43 1!+\binom44 0!\\&=24-24+12-4+1\\&=9\end{aligned}
    (1)
  2. So nine of the 24 arrangements have no fixed point:

    P=924=38=0.375\begin{aligned}P&=\frac{9}{24}=\frac38\\&=0.375\end{aligned}
    (2)
  3. As the number of people grows, the probability tends to 1/e≈0.36791/e≈0.3679: with 4 people it is already close.

Answer924=38\frac{9}{24}=\frac38

wordgptpro.com

Need a hint?

Count the arrangements with no fixed point (derangements) with inclusion–exclusion.

The probability that nobody gets their own hat is 9/24 = 3/8 = 0.375 (about 1/e for many people).

How to work it out

  1. There are 4!=244!=24 ways to return the hats. Inclusion–exclusion on 'someone gets their own hat':

    !4=4!−(41)3!+(42)2!−(43)1!+(44)0!=24−24+12−4+1=9\begin{aligned}&!4\\&=4!-\binom41 3!+\binom42 2!-\binom43 1!+\binom44 0!\\&=24-24+12-4+1\\&=9\end{aligned}
    (1)
  2. So nine of the 24 arrangements have no fixed point:

    P=924=38=0.375\begin{aligned}P&=\frac{9}{24}=\frac38\\&=0.375\end{aligned}
    (2)
  3. As the number of people grows, the probability tends to 1/e≈0.36791/e≈0.3679: with 4 people it is already close.

LaTeX source of the formulas on this page
\[ \frac{9}{24}=\frac38 \]
\[ !4=4!-\binom41 3!+\binom42 2!-\binom43 1!+\binom44 0!=24-24+12-4+1=9 \]
\[ P=\frac{9}{24}=\frac38=0.375 \]

Questions

What is the answer to: The hat-check problem for 4 people?

The probability that nobody gets their own hat is 9/24 = 3/8 = 0.375 (about 1/e for many people).

What is the key idea?

Inclusion–exclusion counts permutations with no fixed point.

Is there a hint?

Count the arrangements with no fixed point (derangements) with inclusion–exclusion.

Related problems

More probability and puzzles

    The hat-check problem for 4 people: answer and solution | WordGPT