4

# I have to answer this problem to land a job interview!!

1
Sun 23 Dec, 2007 02:28 pm
I don't own a coat. Problem solved
0 Replies

Quincy

1
Sat 26 Jan, 2008 05:24 am
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.
0 Replies

makar

1
Fri 30 Jan, 2009 10:47 am
@g day,
i agree with u
0 Replies

1
Fri 30 Jan, 2009 10:53 am
@markr,
Doesn't that assume that the first person took the wrong coat?

1
Fri 30 Jan, 2009 10:54 am
0 Replies

fresco

2
Fri 30 Jan, 2009 11:20 am
I agree with 1/2, but I think the selection procedure is a bit tough for a cloakroom attendent.
0 Replies

makar

1
Fri 30 Jan, 2009 11:55 am
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
0 Replies

makar

1
Fri 30 Jan, 2009 12:04 pm
0 Replies

vinsan

1
Fri 30 Jan, 2009 01:14 pm
Hi Guys,

This is the classic riddle of probability

refer this...

http://discuss.fogcreek.com/techInterview/default.asp?cmd=show&ixPost=504
0 Replies

fresco

1
Fri 30 Jan, 2009 01:27 pm
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

1
Fri 30 Jan, 2009 05:48 pm
@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

Notice that the last guy either gets his own coat or the first guy's coat 50% 0f the time.

1
Fri 30 Jan, 2009 05:55 pm
@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.
0 Replies

fresco

1
Fri 30 Jan, 2009 06:32 pm
@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

1
Fri 30 Jan, 2009 07:01 pm
@fresco,
erratum

Binary codes 0 to 2^(n-1) -1
0 Replies

bloosmudge

1
Thu 25 Jun, 2009 04:48 am
I think that you are all very good ... I'm confused ... if the coat fits and yours is gone ... take it ;p
0 Replies

### Related Topics

Evolution 101 - Discussion by gungasnake
Typing Equations on a PC - Discussion by Brandon9000
The Future of Artificial Intelligence - Discussion by Brandon9000
The well known Mind vs Brain. - Discussion by crayon851
Scientists Offer Proof of 'Dark Matter' - Discussion by oralloy
Blue Saturn - Discussion by oralloy
Bald Eagle-DDT Myth Still Flying High - Discussion by gungasnake
DDT: A Weapon of Mass Survival - Discussion by gungasnake