Associated Topics || Dr. Math Home || Search Dr. Math

### 30 hat probability question

```
Date: Mon, 7 Nov 1994 22:38:49 -0800 (PST)
From: Victoria Gong
Subject: Re: probability...

I'm a high school student at Lynbrook hs in West San Jose,
California and I got "stuck" on this probability problem...

In a department store there are 30 cubbies of different hats.
Each hat has its own assigned cubbie box. However, there was
an earthquake...and all of the hats fell onto the floor (out
of their cubbies) and then the department store lady tried to
put back the hats into their cubbies...so randomly she placed
one hat here...and one hat there until 30 hats were in the
cubbies (one per cubbie). However, of course, the store lady did
not know which hat went with which cubbie, so some of the cubbies
had the wrong hat in them... the question is: what is the probability
that at least one hat will be in its properly assigned cubbie?

so I was thinking that it would be...

p = 1 - (complement of p)

but if I just did it regularly (not using the complement way)
the probability would have a denominator of 30! right?
but I have no idea how to get the numerator...

with 2 hats: p = 1/2
with 3 hats: p = 2/3
with 4 hats: p = 15/24

I think that those above are correct...
but I can't find a certain pattern...
and I'm getting really frustrated!!!

do you know how to do the problem?
thanks.
vg.
```

```
Date: Mon, 7 Nov 1994
From: Demetri Bonaros
Subject: Re: probability...

This is, indeed, a rather tricky problem. I remember having some
trouble with things like this when I first got introduced to probability.

First, let's think about what the statement "the probability that
exactly one of the hats ends up in the right cubbie" means. It means
that one hat is in the right cubbie and all the others are in the wrong
cubbies. Well, this probability for, say, hat A, would be
1/30*(29/30)^29 (can you see why?)

Therefore, the probability for any one of the hats would be the
expression above times 30. You see that this doesn't have a
denominator of 30.

Now, can you see what the probability that exactly two hats are in
the right cubbies is? How about three hats? If you keep going in the
same manner and then add all the numbers you find, you should get

Of course, it is much easier, as you said, to solve this by taking into
consideration the property p = 1 - (complement of p). Given the
discussion above, can you derive an expression for the complement
of p? If yes, you're set. If not, well, just right back. We'll be here to
2, 3 and 4-hat cases?

Demetri- Dr, or somethin'.
```

```
Date: Mon, 7 Nov 1994 22:41:34 -0800 (PST)
From: Victoria Gong
Subject: Re: probability...

noooooo...i mean 30! (30 factorial) as the denominator...

btw, is there a better method than to add all of the sums of
one hat, two hats, three hats, four hats...?

thanx,
victoria
```

```
Date: Tue, 8 Nov 1994 01:55:17 -0500
From: Demetri Bonaros
Subject: Re: probability...

My fault, I didn't realise that you meant factorial. Still, the
denominator is not n! for n hats. Let's look at the case of two hats: the
probability (call it p) that at least one of them is in the right cubbie is
equal to one minus the pr. that none of them is in the right cubbie. The
pr. that none of them is in the right cubbie is 1/2 for the first hat times
1/2 for the second, ie 1/4. Therefore, our expression is p = 1 - 1/4 = 3/4
For three hats, this would be

1 - 2/3*2/3*2/3 = ...

As for what is an easier way to solve this problem, why it is the exact
method that you suggested ( 1- (complement of p)).

Hope this makes sense. If not, do write back!

Demetri- Dr, or somethin'.
```

```
Date: Mon, 7 Nov 1994 23:01:37 -0800 (PST)
From: Victoria Gong
Subject: Re: probability...

I know how to get the probability for 1, 2, 3, or 4 hats...
but to get the probability for 30 hats is kind of hard...
for some reason I think that the "complement" approach would
be much harder than the other way...

it's something like...  X       right? where X = the p(1 hat) + p(2)
----         + p(3) + p(4) ... p(30) right?
30!

is there some sort of equation that encompasses all of the
sums? I mean...hmm...this is quite confusing...
```

```
Date: Wed, 9 Nov 1994 10:10:21 -0500
From: Anonymous
Subject: Re: probability...

Victoria, you might have noticed that there looks to be a pattern in
the probability that no hat ends up in the right place:

1/2!,2/3!,9/4!,44/5!,265/6!

In particular, we might as well focus on generating the numerators
since the denominators are obvious: 1,2,9,44,265 . . .

You have already realized that the subsequent trials include the results
of the previous trials in some way. See if you can find a relationship
between the numerators and n.  In other words, the way I worked on it,
I assumed there must be something I can do with the numerator (or
numerators) that came before and the n of the version I'm trying to
calculate that would give me the new numerator.

I found several different ways to manipulate numerators and n to get the
next numerator.

Try it.  I'll send the final answer given by one of our math doctors,
Ethan, after I've heard back from you.

-- steve ("chief of staff")
```

```
Date: Tue, 15 Nov 1994 23:03:57 -0500
From: Anonymous
Subject: Re: probability...

(Victoria, I haven't heard back from you but I couldn't stand the idea of
wasting Ethan's answer so here it is.  -- steve)

Hi Victoria,

I am sorry that it took me so long to get on the hats in the cubbies
problem.  I saw that people were on it and assumed that it was cool.
Sorry.

THIS IS A HARD PROBLEM THIS IS A HARD PROBLEM.
DO NOT BE DECEIVED. THERE IS NOTHING TRIVIAL ABOUT
THIS BABY.

Okay, here's the deal.

One of the earliest statements of this problem also involved hats and it
was in Montmort's probability book, published in 1708.

Essentially this problem can be represented as a permutation, i.e. how
many ways can you arrange the numbers 1 through 30?  And we want
to know first how many permutations move every spot ( the formal
way to say this is that they have no fixed points). Then we divide this
number by the total possible permutations and we get the proability
that no hats are in the place where they belong.

Well this ain't easy. I will tell you the answer and if you want to
see the proof I would direct you to read pages 90 through 100 of
_Introduction to Probability_, J. Laurie Snell.

It turns out that the proablity that for n hats that no hat ends up in its
right spot is:

1/2! - 1/3! + 1/4! - 1/5!    + (-1)^n/n!

And those of you who really remember your Taylor series will know
that this gets to 1/e really fast.

So for your question with n = 30,  this puppy is reallllly close to
just being 1/e.  I mean real close.

Ethan - Doctor taking too long to getting around to being on call
```

```
Date: Thu, 17 Nov 1994 19:47:03 -0800 (PST)
From: Victoria Gong
Subject: Re: probability...

* to all the people who helped out on the cubbie/hat problem...
* thanks soooooooooooooooooooooooo much! I understand it now...

>         Well this ain't easy. I will tell you the answer and if you want to
> see the proof I would direct you to read pages 90 through 100 of
> _Introduction to Probability_, J. Laurie Snell.

* ^^^^^--- I think I'll look this one up, to get more info on it,
but at any rate, I really appreciate all of your assistance.

thanks again,
victoria

p.s. even my math teacher got stuck on it too! :)
```
Associated Topics:
High School Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search