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 the answer to your original question. 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 help you some more. Also, can you now check your answers for the 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! :)
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.