I don't own a coat. Problem solved
Just my thoughts.
First guy grabs a coat at random.
Probability it is his: 1/N
Probability it is not: 1-1/N = (N-1)/N
If 1st guy grabs his own coat, then everyone else grabs their own, because they are there. This Happpens with probability 1/N.
Now there are N-1 people left. The Probability the m'th person to leave finds their coat thereafter is the probability that everyone that left before them found their own coat or didn't take the m'th guys coat. That is, er, I dunno, i suppose you smart people here can figure that out!
If 1st guy doesn't grab his own coat, there is a 1/(N-1) that the next guy does NOT find his coat there (ie. the 1st guy took it).
If the 2nd guys' coat isn't there, he grabs one at random, with probability 1/(N-2) it belongs to the next guy. etc.
@markr,
Doesn't that assume that the first person took the wrong coat?
@DrewDad,
Dammit! Tricked into replying to an old thread....
I agree with 1/2, but I think the selection procedure is a bit tough for a cloakroom attendent.
Let required probability be p(n) for n>1
There are two possibilities (i) first person A gets his own coat, prob.=1/n
(ii) first person A randomly takes someone else coat but not the coat of last person,for this n-2 possible choices out of n. Now the person B whose coat was taken by A comes at kth (k=2,3,4 . . .,n-1) position (its probability 1/(n-2)). For him there will be n-k+1 coats available including the coat of A and of the last person. In this case we can rename the coat of A as the coat of B and B is randomly selecting one of the coat out of n-k+1 coats
=> p(n) = (1/n) +[(n-2)/n]*sum from 2 t0 n-1 of [{1/(n-2)}*p(n-k+1)]
= (1/n) +[1/n]*sum from 2 t0 n-1 of p(k)
=> np(n) = 1+sum from 2 t0 n-1 of p(k) --------(1)
=>(n+1)p(n+1) = 1+sum from 2 t0 n of p(k) --------(2)
from (2)-(1), (n+1)p(n+1) - np(n) = p(n)
=>(n+1)p(n+1) = (n+1)p(n)
=>p(n+1) = p(n)
As p(2)=1/2, p(n) = 1/2 for n>1
please give your expert opinion to my solution
Makar,
No complex solution is required.
As the question is worded, either the first guy takes his own coat or not (2 choices not n)and that is true for everybody in the chain, as though the first guy passes his critical decision"as owner or not to each guy in turn but they have no choice of the two states. It becomes the equivalent of a two choice problem passed down the chain, hence p=1/2.
@fresco,
Just to flesh that out a little, here are all the allowable combinations for 3 guys
ABC and 3 coats
abc and also 4 guys
ABCD with coats
abcd. Note that all except
A must choose their own coat if it is there.
Aa Bb Cc
Ab Ba Cc
Ac Bb Ca
Ab Bc Ca
Aa Bb Cc Dd
Ab Ba Cc Dd
Ab Bc Ca Dd
Ab Bc Cd Da
Ab Bd Cc Da
Ac Bb Cd Da
Ac Bb Ca Dd
Ad Bb Cc Da
Notice that the last guy either gets his own coat or the first guy's coat 50% 0f the time.
@fresco,
Yeah, I figured out that the odds of the first guy getting his own coat are offset by the odds of his getting the last guy's coat.
@fresco,
A further observation with respect to binary choice is indicated by writing
1 for owner,
0 for taker in the combinations above
111
001
010
000
1111
0011
0001
0000
0010
0100
0101
0110
It follows that all choices made after the first guy (first binary digit) are represented by the binary codes 0 to (n-1)sqd -1 where n is the number of people. This range obviously ends in an equal number of 1's and 0's
@fresco,
erratum
Binary codes 0 to 2^(n-1) -1
I think that you are all very good ... I'm confused ... if the coat fits and yours is gone ... take it ;p
