Author |
Topic: Umbrella-makers' convention (Read 895 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
Umbrella-makers' convention
« on: Mar 4th, 2004, 12:58pm » |
 Quote  Modify
|
At the umbrella-makers' convention (held, of course, in Manchester, England), everyone arrives with an umbrella. Alas, the umbrellas become mixed up, so that afterward each person is given a random umbrella.
What is the expected value of the number of people who receive their own umbrella?
|
|
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Umbrella-makers' convention
« Reply #1 on: Mar 4th, 2004, 3:26pm » |
Quote Modify
|
This is a bit similar to the insane passenger.., different side of the same coin really..
Still took me surprisingly long to find/understand the answer to this one though 
|
| « Last Edit: Mar 4th, 2004, 3:29pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender:
Posts: 767
|
|
Re: Umbrella-makers' convention
« Reply #2 on: Mar 4th, 2004, 7:08pm » |
Quote Modify
|
Isn't this related to the birthday principle, where it only takes about 100 people before it is almost certain one pair shares a birthday?
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Speaker
Uberpuzzler
Gender:
Posts: 1118
|
|
Re: Umbrella-makers' convention
« Reply #3 on: Mar 4th, 2004, 10:41pm » |
Quote Modify
|
These problems that involve probability or statistical chance always go over my head and limited math skills. How to bookies (who I can assume are not very well educated) decide what the odds are on bets? Do they just have a really good grasp of probability theory? Or, are there some simple methods that someone like me could master. (Remember I only have 10 fingers and 10 toes.)
My answer for this one is:
If nobody leaves until their umbrellas has been given away, then the expected value is zero. Because nobody leaves.
If somebody stands at the door and waits until he sees somebody carrying his umbrella, then the answer is x >=1.
If everybody stands at the door and waits until he sees somebody carrying his umbrella, then the answer is X <=X (where x is the number of participants at the convention)
If everybody ignores their own umbrella and takes the best-looking umbrella they can find (which is likely as these people have an unhealthy interest in umbrellas), then everybody except the last group out the door will get their own umbrella. (You can prove this by asking them,
"Hey buddy, is that your umbrella?!"
"Yeah, it's mine. I left it right here before I went in. So, shutup its none-of-your business!"
So, the value would be X <=50% of the total.
Well, I guess it's not so hard after all.
|
|
IP Logged |
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. <Ben Franklin>
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Umbrella-makers' convention
« Reply #4 on: Mar 5th, 2004, 12:48am » |
Quote Modify
|
You can easily look at the first few cases,
If there is one person, he will leave with his umbrella, so E=1
If there are two people, the chance the #1 get's his own umbrella is 1/2, and the case is then reduced to n=1, so the other gets his own umbrella as well.
If however the first one takes the wrong umbrella, the second person can't get his anymore, so E = 1/2*2+1/2*0 = 1
For three people,
Probability is 1/3 that #1 get's his umbrella, the case then reduces to the case for n=2.
There's 2/3 chance he'll take the wrong umbrella, and then the probability is 1/2 that #2 will take #1's umrella which leaves #3 with his own, otherwise all three end up with the wrong one.
So E = 1/3 * (1+1) + 2/3*1/2 = 1
You may have noticed a trend develloping, now just try and prove it.. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Speaker
Uberpuzzler
Gender:
Posts: 1118
|
|
Re: Umbrella-makers' convention
« Reply #5 on: Mar 5th, 2004, 1:14am » |
Quote Modify
|
Okay a trend.
I see that the first part of the equation is the chance of success.
1/2 or 1/3 or 1/x (where x is the number of people)
Then the second part is describing the possibility of success after the first person leaves.
But, what is the (1+1) in the middle? Anyway I get this.
E = 1/x * (1+1) + x-1/x*x-2/x-3=
Which is of course wrong, but where?
|
| « Last Edit: Mar 5th, 2004, 1:16am by Speaker » |
IP Logged |
They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety. <Ben Franklin>
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Umbrella-makers' convention
« Reply #6 on: Mar 5th, 2004, 2:09am » |
Quote Modify
|
in E = 1/3 * (1+1) + 2/3*1/2 = 1
the '(1+1)' comes from (1 + E2), #1 get's his own umbrella plus #2 get the expected number of correct umbrellas from case n=2 (which is E2)
likewise
E4 = 1/4 * (1 + E3) + 3/4*something else
En = 1/n * (1 + En-1) + (n-1)/n * something
It's of course the 'something' that's tricky 
Just think about what happens for the rest of the people is the first one doesn't get his own umbrella.
|
| « Last Edit: Mar 5th, 2004, 2:11am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
Gender:
Posts: 767
|
|
Re: Umbrella-makers' convention
« Reply #7 on: Mar 5th, 2004, 6:24am » |
Quote Modify
|
on Mar 5th, 2004, 2:09am, towr wrote:| Just think about what happens for the rest of the people is the first one doesn't get his own umbrella. |
|
At least one other person does not get his umbrella. I see where you are going with your probabilities. I figured it would be slightly higher, maybe ln (x).
To put this in computer terms I can understand, if a person x is assigned a unique number and the array u contains umbrellas with matching numbers,
[smiley=forall.gif] x1 != u[x1], [smiley=exists.gif] x2 != u[x2]
The probability of the first guy taking the correct umbrella is n-1, where n is the number of people. For the second case, we need to do something with conditional probability. And from there it looks like it would be a messy binary tree of probabilities, although I imagine it would simplify to something very easy using mathematical induction.
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
adelbert
Guest
|
|
Re: Umbrella-makers' convention
« Reply #8 on: Mar 5th, 2004, 6:49am » |
Quote Modify
 Remove
|
I don't know much about probabilities, but it seems to simplify down to each individual has a 1/n chance of getting his own umbrella. Multiply by n and you get the answer 1. I assume the reason you don't have to go through all the complications of "what is the probability of the second person getting his own, provided that the first did or didn't get his" is that we're just looking at the average over all situations, so the problem is the same as asking, if one person picked an umbrella at random n times, how many times would he pick his own.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Umbrella-makers' convention
« Reply #9 on: Mar 5th, 2004, 7:55am » |
Quote Modify
|
I think adelbert is right (this argument works because of the "linearity of expectation").
on Mar 4th, 2004, 3:26pm, towr wrote:
I don't see similarity... Try, for example, to find the probability that no maker gets his own umbrella. (I can't believe this classical puzzle isn't on the site).
|
|
IP Logged |
|
|
|
NickH
Senior Riddler
Gender:
Posts: 341
|
|
Re: Umbrella-makers' convention
« Reply #10 on: Mar 5th, 2004, 1:03pm » |
Quote Modify
|
When I saw this puzzle a few days ago, the number of people was given as 8. It was also a four part question, the other three parts asking for:
(a) the probability of no matches;
(b) the probability of exactly 4 matches;
(c) the least likely number of matches.
Part (c) was easy: 7 matches is the only impossible outcome.
Part (a) I've seen before: the answer involves derangements (http://mathworld.wolfram.com/Derangement.html). The required probability is d(8)/8!, where d(8) is the number of derangements of 8 elements.
For part (b), you can fix 4 elements, then count the derangements of the remaining 4. Multiply by C(8,4) to get the total number of such arrangements.
Having done this, I naturally went on to calculate the expected value of the number of matches by summing from m = 0 to 8 (C(8,m) * d(8-m))/8!. When I found the answer was 1, I suspected there must be an easier solution!
|
|
IP Logged |
Nick's Mathematical Puzzles
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print