12 men leave their hats with the hat check.
probability/derangement Added material
Problem
12 men leave their hats with the hat check. If the hats are randomly returned, what is the probability that nobody gets the correct hat?
Show solution
Suppose we are handing out hats to n people. First we start with all the possible outcomes. Then we subtract off those that assign the right hat to a given person, for each of the n people. But this double-counts each outcome that assigned 2 hats correctly, so we have to add those outcomes back in. But now we've counted one net copy of each outcome with 3 correct hats in our set, so we have to subtract those off again. But now we've taken away each 4-correct-hat outcome once too often, and have to put it back in, and so forth ... until we add or subtract the outcome that involves all n people getting the correct hats. Putting it all in probabilities, the measure of the original set is 1. For a given subset of k people, the probability that they all get their correct hats is (n-k)!/n!, while there are (n choose k) such subsets of k people altogether. But then (n choose k)*(n-k)!/n! = (n!/((n-k)!*k!))*(n-k)!/n! = 1/k! is the total probability measure we get by counting each subset of k people once each. So we end up generating the finite series 1 - 1/1! + 1/2! - 1/3! +- ... +/- 1/n! which is of course just the first n+1 terms of the Taylor series expansion for f(x) = e^x centered at 0 and evaluated at -1, which converges to 1/e quite fast. You can compute the exact probability for any n >= 1 simply by rounding n!/e to the nearest whole number, then dividing again by n!. Moreover I think you will find you are always rounding down for odd n and rounding up for even n. For example, 12! / e = 176214840.95798... which is within 0.05 (absolute error, not relative) of the correct intermediate result, 176214841. Another fact is that if you set the probability of no matching hats equal to m/n!, then m is an integer divisible by (n-1). That's because the number of ways you can give hat #2 to person #1 is exactly the same as the number of ways you can give that person hat #3, likewise for hat #4, and so forth. -- David Karr (karr@cs.cornell.edu)
Additional material
[ Editor: A derivation by recurrence, for N people: ]
The chance of a Total MisMatch is unaffected by the order in which the
N people retrieve their hats. Denote the first retriever as person #1.
Assume that if he doesn't retrieve his own hat, the person whose hat
he retrieved goes 2nd (and is denoted #2). There are then 3
meaningful cases:
Case 1: #1 retrieves his own hat [P = 1/N]
Case 2: #1 retrieves #2's hat and #2 retrieves #1's hat
[P = ((N-1)/N) x 1/(N-1) = 1/N]
Case 3: #1 retrieves #2's hat and #2 retrieves someone else's
[P = ((N-1)/N) x (N-2)/(N-1) = (N-2)/N]
It remains to discard Case 1, and find the chances of a Total MisMatch
in Cases 2 and 3.
Let F(N) denote chance of a Total MisMatch among N people.
G(N) denote chance of a Total MisMatch given that the 1st 2
people retrieve each other's hats (re Case 2 above).
H(N) denote chance of a Total MisMatch among N people, given
that #1 retrieves #2's hat, and #2 retrieves someone
else's (re Case 3 above).
Then F(N) = [G(N) x (1/N)] + [H(N) x ([N-2]/N)].
In Case 2 above, with hats #2 and #1 retrieved by people #1 and #2
respectively, hats #3, #4, ..., #N remain and people #3, #4, ..., #N [ Editor: ".., #N" in the original ]
remain. This is identical to the general chance of a Total MisMatch
among N-2 people.
Thus G(N) = F(N-2).
In Case 3 above, with #1 retrieving hat #2, denote the hat retrieved by
person #2 as hat #3. Then people #3, #4, #5, ..., #N remain and hats
#1, #4, #5, ..., #N remain. This is (effectively) identical to the
chance of a Total MisMatch among N-1 people (who might be numbered #1,
#3, #4, #5, ... #N), given that #1 did not retrieve his own hat (e.g.
he retrieved hat #3 instead).
Thus H(N) x [(N-2)/(N-1)] = F(N-1), so
H(N) = F(N-1) x [(N-1)/(N-2)]
So F(N) = [F(N-2) x (1/N)]
+ {F(N-1) x [(N-1)/(N-2)] x [(N-2)/N]}
= [F(N-2) x (1/N)] + [F(N-1) x (N-1)/N]
= {(1/N) x [F(N-2) - F(N-1)]} + F(N-1)
Thus F(N) - F(N-1) = (1/N) x (-1) x [F(N-1) - F(N-2)]
Note that F(0), which may be construed as probability that "no one"
gets their hat, among zero [ Editor: "Zero" in the original ] people, may be (arbitrarily) set = 1. Let
A^B denote A raised to the Bth power. Then,
F(1) - F(0) = [(-1)^1] x 1/(1!)
F(2) - F(1) = [(-1)^2] x 1/(2!)
F(3) - F(2) = [(-1)^3] x 1/(3!)
...
F(N) - F(N-1) = [(-1)^N] x 1/(N!)
Thus
F(N) = F(0) + [F(1) - F(0)] + [F(2) - F(1)] + ... + [F(N) - F(N-1)]
= 1 + -1/1! + 1/2! -1/3! + ... - ... + [(-1)^N] x 1/(N!)
For calculus [ Editor: "Calculus" in the original ] aficionados, the transcendental e (approx 2.71828+) raised
to the xth power is given by the infinite sum of:
1 + (x^1)/1! + (x^2)/2! + (x^3)/3! + ...
Thus as N --> infinity, F(N) --> e^(-1) = 1/e (approx .36787+)
-- Steve Schooler <stevesch@ix.netcom.com>
**********************************************************************
[ Editor: Variant: ] N men leave their hats with the hat check, and then the hats
are randomly returned. On average, how many men will get their own
hats back?
The answer is 1. This can be shown very easily.
-- David Karr <karr@cs.cornell.edu>
**********************************************************************
[ Editor: Variant: ] Five paychecks and envelopes are addressed to five different
people. If the paychecks are randomly inserted into the envelopes,
what is the probability that (a) EXACTLY one will be inserted in the
correct envelope and (b) AT LEAST one will be inserted in the correct
envelope? [ Editor: posed by David Blais <dblais@indirect.com> ]
If P(A) is probability that letter A is in correct envelope A, P(B) is
probability that letter B is in the correct envelope B and so on, then
the probability that only A is in correct envelope is
[ Editor: "is =" in the original ] P(A)(1 - P(B or C or D or E)).
The number of ways we can select the one correct letter is 5C1 = 5,
and so the probability that exactly one is correctly posted is
5.P(A)(1 - P(B or C or D or E))
Now P(A) = 1/5 and also we have
[ Editor: an unmatched ")" after "E" removed below ]
P(B or C or D or E) = P(B) + P(C) + P(D) + P(E) - 4C2.P(B and C)
+ 4C3.P(B and C and D) - P(B and C and D and E)
= 1/4 + 1/4 + 1/4 + 1/4 - 6(1/4)(1/3) + 4(1/4)(1/3)(1/2)
- (1/4)(1/3)(1/2)(1/1)
= 1 - 1/2 + 1/6 - 1/24
= 5/8
And so required probability = 5(1/5)(1 - 5/8) = 3/8
Next we require probability that at least one letter is in correct
envelope. This is the same as P(A or B or C or D or E)
= P(A) + P(B) + P(C) + P(D) + P(E) - 5C2.P(A and B) + 5C3.P(A and B and C)
- 5C4.P(A and B and C and D) + P(A and B and C and D and E)
= 5(1/5) - 10(1/5)(1/4) + 10(1/5)(1/4)(1/3) - 5(1/5)(1/4)(1/3)(1/2)
+ (1/5)(1/4)(1/3)(1/2)(1/1)
= 1 - 1/2 + 1/6 - 1/24 + 1/120
= 19/30
And so the two answers are
(a) EXACTLY one is correct. Probability = 3/8
(b) AT LEAST one is correct. Probability = 19/30
-- Anthony Hugh Back <tony2back@aol.com>
[ Editor: from a May 1996 rec.puzzles thread "Payroll Mix-Up". ]
In a previous article, dblais@indirect.com (David Blais) says:
>Five paychecks and envelopes are addressed to five different people.
>If the paychecks are randomly inserted into the envelopes, what is the
>probability that (a) EXACTLY one will be inserted in the correct
>envelope and (b) AT LEAST one will be inserted in the correct
>envelope?
>
>I have solved this problem for 1,2,3,4 paychecks/envelopes (using a
>brute force method), but can't seem to find a pattern for n
>paychecks/envelopes. Is there a formula for n paychecks/envelopes?
This problem is an analogue of two rather famous problems. The first
is the 'derangement' and the second is the 'probleme des rencontres'.
The general solution to these types of problems is derived from the
application of the principle of INCLUSION/EXCLUSION, an explanation of
which can be found in most elementary combinatorics texts.
What's a 'rencontre'? ........ Given a set of ordered objects
{a,b,c,d,e} there are 5! permutations. Of these 120 permutations, we
wish to know, how many have objects in their correct initial positions.
A permutation that has one(1) object in its correct position is a
'rencontre' of one(1), etc.
Order: abcde abcde abcde abcde abcde abcde
Permutation: acbed bcdea baced dbace abced badec
^ ^ ^ ^ ^^^
Rencontre: r=1 r=0 r=1 r=2 r=3 r=0
Rencontres of zero(0) are known as 'derangements' .......................
To determine the exact quantity of these permutations, for N objects
and (r=0 to N) 'rencontres', the following equations may be used;
N := Total number of objects
r := (0 to N) Number of 'rencontres' [mutually exclusive]
q := 0,1,2 .... (N-r) Summation Indexing Variable
k := Number of permutations of r 'rencontres' [discrete]
_ _
N-r | (q) |
N! | (-1) |
k := -- * SUM | --------- |
r! | q! |
q=0 |_ _|
Here, is an equation that was developed by David Karr
(karr@cs.cornell.edu) that can be executed entirely on a handheld
calculator, using (e) as a constant, with exact results. (FLOOR = use
the integer portion only).
N := Integer N > 0
r := Integer (r => 0 < N)
e := 2.7182 8182 8459 (constant)
- - - - - -
| N! | | | (N-r)! | 1 |
k := |-----------| * FLOOR | | -------- | + - |
| (N-r)!*r! | | | e | 2 |
- - - - - -
NOTE: k := 1 (If N = r)
With the above equations you can now determine all of the various
possible outcomes with respect to the distribution of "N" pay checks
and envelopes.
Here's a table for N=1 to N=8:
N|r 0 1 2 3 4 5 6 7 8 N!
-------------------------------------------------------------------
1 0 1 - - - - - - - 1
2 1 0 1 - - - - - - 2
3 2 3 0 1 - - - - - 6
4 9 8 6 0 1 - - - - 24
5 44 45 20 10 0 1 - - - 120 *
6 265 264 135 40 15 0 1 - - 720
7 1854 1855 924 315 70 21 0 1 - 5040
8 14833 14832 7420 2464 630 112 28 0 1 40320
-------------------------------------------------------------------
Therefore, the probability that EXACTLY one(1) pay check will be in its
correct envelope is 45/120 = .375 and the probability that at LEAST
one(1) pay check will be in a correct envelope is 76/120 = .633.
-- David J. Snook <ah766@yfn.ysu.edu>