Once his noodle-soup arrives, he gets to work. He extracts two noodle ends from under the soup, ties a knot, and lets it slip into the soup again. He does the above 100 times - so that now all the noodle 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?
Solution: I attacked this problem from various directions because I was not sure of the direction. This led to a lot of confusion and more thoughts until the number of thoughts were growing combinatorically at a prohibitive rate. I finally landed upon the solution though and wore the garland.
I am initially presenting the other approaches and solutions. It is left to the reader (if any) to determine why each one is correct or incorrect. The correct solution is presented at the last.
Solution 1: This was the first one I came up with. Let us the consider the case of failure of formation of the garland. This might happen if he shorts a noodle at the first attempt, or if he shorts it at the second attempt, and so on. The probability that he shorts a noodle at the first attempt is given by 100/(200C2). This is because two noodle ends may be chosen in 200C2 ways and a noodle may be shorted in 100 ways (since there are 100 noodles). The probability that he shorts a noodle at the second attempt is 99/198C2, and so on. Therefore, the probability of failure is given by:
[formula being created using math symbols .. coming soon]
And, the probability of success is P = 1 - P'. For example, if there are 2 noodles, then the probability of success comes out to be 2/3, while for the case of 3 noodles, the probability of success comes out to be 7/15.
Solution 2: The process of selecting a noodle end may also be considered to be the process of selecting a noodle itself. In this case, when we select two noodle ends, we are selecting 2 noodles with repetition allowed. This is another way of looking at the problem. Consider the 2-noodle case where the noodles are named A and B. Then there are 3 possibilities for selecting two noodles - (A,A), (B,B) and (A,B). Only case is favorable to us and hence the probability of success is 1/3.
In the 3 noodle case, there will be 2 steps of noodle selection. For the first step, we 6 possibilities: (A,A), (B,B), (C,C), (A,B), (B,C), (A,C). After this, the second step is nothing but the 2-noodle case. Each of these cases will generate 3 more cases for a total of 18 cases. 9 of these are rejected. Further, for the (A,B), (B,C), (A,C), only one of the 3 cases generated for each is favorable. Hence, only 3 cases are favorable. The answer is therefore 3/18 = 1/6. However, this argument is getting complicated and as confusing as a lump of noodles.
Solution 3: In the above solution, observe that many cases are repeated. Consider the 3-noodle case. Starting from (A,A) we may reach the case where all 3 noodles are shorted. But this may also be reached from (B,B) and (C,C). Also, the noodles are really indistinguishable from one another. Perhaps, we should be considering only the configurations that we land up with at the end of the noodle-ends tying process.
In that case, for the 2-noodle case, only 2 configurations are possible:
1 1 (both noodles shorted)
2 (garland formed)
For the 3-noodle case, only 3 configurations are possible:
1 1 1 (all three noodles shorted)
1 2 (a garland of two noodles shorted and another single noodle shorted)
3 (garland formed)
These are nothing but the partitions of the number, and therefore the probability is then 1/p(100) where p(100) denotes the number of partitions of 100. In general, the probability is 1/p(n).
Correct Solution: This solution is actually a corrected version of Solution 1. What did we miss out in Solution 1 then ? We are considering the cases of failure. He may either fail at the first step by shorting a noodle or he may fail at the second step by shorting a noodle, and so on. More precisely, he may fail at step i if he shorts a noodle at step i and has not shorted any noodle in the previous (i-1) steps. We had missed out this "and part" in calculation of the probabilities !
Therefore, for the 3 noodle case, we have:
P' = 3/(6C2) + (1 - 3/(6C2))(2/4C2) = 1/5 + 4/5 * 1/3 = 1/5 + 4/15 = 7/15
and
P = 1 - P' = 1 - 7/15 = 8/15
Similarly, for the 100 noodle case.
[formula being created using math symbols - coming soon].
Enough of noodles. I am not going to eat them for a long time now. And even if I decide to do so, who knows ? I might end up trying to form a garland after all.
No comments:
Post a Comment