wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Umbrella-makers' convention
        
(Message started by: NickH on Mar 4^th, 2004, 12:58pm)

Title: Umbrella-makers' convention
Post by NickH on Mar 4^th, 2004, 12:58pm

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?

Title: Re: Umbrella-makers' convention
Post by towr on Mar 4^th, 2004, 3:26pm

This is a bit similar to the insane passenger.. (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1067088849), different side of the same coin really..
Still took me surprisingly long to find/understand the answer to this one though ::)

Title: Re: Umbrella-makers' convention
Post by John_Gaughan on Mar 4^th, 2004, 7:08pm

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?

Title: Re: Umbrella-makers' convention
Post by Speaker on Mar 4^th, 2004, 10:41pm

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. ::)

Title: Re: Umbrella-makers' convention
Post by towr on Mar 5^th, 2004, 12:48am

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.. 8)

Title: Re: Umbrella-makers' convention
Post by Speaker on Mar 5^th, 2004, 1:14am

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?

Title: Re: Umbrella-makers' convention
Post by towr on Mar 5^th, 2004, 2:09am

in E = 1/3 * (1+1) + 2/3*1/2 = 1
the '(1+1)' comes from (1 + E₂), #1 get's his own umbrella plus #2&#3 get the expected number of correct umbrellas from case n=2 (which is E₂)

likewise
E₄ = 1/4 * (1 + E₃) + 3/4*something else
E_n = 1/n * (1 + E_n-1) + (n-1)/n * something
It's of course the 'something' that's tricky :P
Just think about what happens for the rest of the people is the first one doesn't get his own umbrella.

Title: Re: Umbrella-makers' convention
Post by John_Gaughan on Mar 5^th, 2004, 6:24am

on 03/05/04 at 02:09:29, 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 [hide]ln (x)[/hide].

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] x₁ != u[x₁], [smiley=exists.gif] x₂ != u[x₂]

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.

Title: Re: Umbrella-makers' convention
Post by adelbert on Mar 5^th, 2004, 6:49am

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.

Title: Re: Umbrella-makers' convention
Post by Barukh on Mar 5^th, 2004, 7:55am

I think adelbert is right (this argument works because of the "linearity of expectation").

on 03/04/04 at 15:26:18, towr wrote:

This is a bit similar to the insane passenger.. (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_easy;action=display;num=1067088849)...

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).

Title: Re: Umbrella-makers' convention
Post by NickH on Mar 5^th, 2004, 1:03pm

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!