The cook in the noodle shop
After a tiresome day boiling vegetables, the cook sits down in the corner of his dingy kitchen for dinner. As is his quaint habit, he puts exactly 100 noodles in his soup and begins his ritual:
He extracts two noodle ends from the bowl, ties a knot and slips it back into the soup. He repeats this 100 times until all the ends are tied. Now, he reaches his hand into the soup.
What is the probability that he would extract a garland containing all the 100 noodles?
credits: tuku
He extracts two noodle ends from the bowl, ties a knot and slips it back into the soup. He repeats this 100 times until all the ends are tied. Now, he reaches his hand into the soup.
What is the probability that he would extract a garland containing all the 100 noodles?
credits: tuku
posted by littlecow at 12/29/2005 11:21:00 AM
10 Comments:
assuming n noodles, the probability will be (n!*2^n)/((2n)!). For 100 noodles, probability comes out to 1.5e-187.
reasoning: n noodles have 2n ends. thus, they can be chosen (and thus tied) in
(2n.c.2)*((2n-2).c.2)*...(2.c.2) ways =
(2n)!/2^n ways. (pick 2 ends out of 2n, then 2 more out of 2n-2 etc..)
one of the ways they can be tied is to line them all up and tie the back end of the first to the front end of the second, back end of second to front end of third and so on till the back end of the nth one to the front end of the first. this will create a garland of noodles. but this arrangement is only one way of lining up all the n noodles. there are n! ways to line them up.
thus, (n!)/((2n)!*2^n) or (n!*2^n)/((2n)!)
The probability is (198/199)*(196/197)*(194/195).....*(4/5)*(2/3).
This is my reasoning - There are totally 200 ends. Choose any end. Then there are 199 ends left. One of these is the other end of the noodle that was selected. So the probability of choosing an end not belonging to the same noddle is 198/199.
Now there are 99 noodles and 198 ends. By a similar reasoning as above, the probability of tying the ends of two different noodles is 196/197.
Since each event is independent of the prior event, the total probability that at the end the chef would have a 100 noodle garland is 198*196*194...*2)/(199*197*195...*3).
raju, your solution is acceptable if the problem is without replacement (noodles are not put back in). but the noodles are put back in. althought it is still a "without replacement" problem for the ends that are tied, your solution does not take into account the free end being put back into the bowl.
Further, the solution assumes sequential progression of the garland and does not capture intermediate chain link events such as tying some kth and (k-1)th noodles as f(k-1) to bk and those noodles later getting tied back together to the main chain. It's rather complicated to solve "with replacement" problems with this approach, IMHO.
balaks, any comments ?
I don't understand the with/without replacement funda. With every knot, two free ends are done away with. Then the new longer noodle is put back into the soup. Then you choose any two noodle ends and tie them together.
The probability by my reasoning is similar to the one you gave - it comes to ((n-1)!*2^(n-1))^2/((2n-1)!).
So the probability by my reasoning comes to 0.088 or something for 100 noodles. I am surprised by such a high value.
Also, according to your solution, Raju, the initial noodle end can be chosen in 200 ways. So, you have to multiply 0.088 by 200, which gives an impossible probability.
With replacement, you put the noodle back in, and the end that is untied is added to the pool.
Without replacement, you take out of the pool both ends of the noodle that was involved in the last tie event.
You are right in cutting out two ends per tie event, but it is the sequential progress and the choice of the same noodle for the next tie event that is debatable.
@lenscrafter: i am afraid raju's solution is the right one - your solution has some counting issues. for ex, n=2 gives a total of 6 cases using 2n!/2^n. however, only 3 cases exist in reality (corresponding to (a) both noodles tied into 2 loops separately, (b) noodle 1 and noodle 2 tied into a single loop in two different ways). in calculating the total number of cases, you included the order in which the ends were chosen. for example, if there were two noodles and you were counting the single loops that can be made, according to your logic, you would have 2C1.1C1 ways of doing it (viz choose one end, tie it to the other end of the same noodle and then, choose one out of the remaining end and tie it... etc) - but there is really only one way of doing it! the ordering accounts for an additional n! which need to be removed from each of the cases to give a total of 2n!/n!/2^n cases.
your number of favorable cases is also underestimated: note that n noodles can be arranged in a circle in (n-1)! ways and not n! (providing for the circular ordering which counts the same linearly ordered cases n times). But in each of these cases, every noodle can be reversed - providing (n-1)!*2^(n-1) total favorable cases instead of the n! you had calculated.
this answer is the same as that of raju's!
@raju: good job!
ok ok i understand now. seems to be some sort of apparent contradiction though: choosing the initial noodle can be done in 200 ways, even though the probabilities are the same whichever noodle you start with. so shouldn't there be 200 different starting ways to achieve the same end result ?
@lenscrafter: what is the contradiction?
you can reach the same outcome by starting out 200 different ways, each of which has the same probability. so shouldn't one add all the probabilities of each event to get the probability of the final outcome ?
grenade, ok now i finally understand. thanks for beating it into my head.
Post a Comment
<< Home