There is a pot of N noodles. (so there are 2N ends). A person randomly grabs two ends and merges them. The person keeps doing it, until there are no more noodles, (and only loops), left in the pot. what’s the average number of loops in the pot?
Solution
OK, all the answers so far just list formulae, without giving any explanation. I’ll try to work it out out loud. (At this point I have no idea what the answer is.) Also, it’s a math problem, so I’ll assume we can ignore factors like how much the noodles stick together, how stiff they are, and so on. I’m sure I have no idea to take account of those factors.
Call the first end he picks up Noodle i. The second end he picks up is Noodle i*.
When he sticks the first two ends together, there are two possible outcomes:
(a) i* is the other end of noodle i, so he has created a loop.
(ii) i* is a different noodle from i, so he has created one long noodle out of two.
What are the odds of (a) happening? There are (2n-1) ends left in the bowl once he picks up the end of noodle i, and only 1 of them is the other end of the same noodle. Abstracting away from all physical details, let’s say the odds of getting the other end of the same noodle are 1/(2n-1).
So the odds of (b) happening are 1-[1/(2n-1)], which is [(2n-1)-1]/(2n-1), i.e. (2n-2)/(2n-1).
If (a) happened, now we have a bowl with one loop in it, and n-1 other unlooped noodles. We add 1 to our count of loops, and repeat the problem for n-1.
If (b) happened, now we have a bowl with 0 loops in it, and n-1 other unlooped noodles. It’s just that one of those noodles is especially long. We don’t add anything to our count of loops; we just repeat the problem for n-1.
Now, when we get down to 1 unlooped noodle left in the bowl, the odds of (a) happening are 1.
The average # of loops will be: for each point where a loop could be formed, add 1 * the probability of a loop being formed then.
So we can write a function:
real average_number_of_loops (int n) if (n == 1) {return 1} else {
— there is a 1/(2n-1) chance of getting 1 loop formed here
— and a (2n-2)/(2n-1) chance of getting 0 loops formed here
— and in either case we then have the same problem repeated for
— n-1 noodles
— so we should return ([(1/(2n-1))*1] + [(2/(2n-1))*0]) + average_number_of_loops(n-1)
— or, simplifying…
return (1/(2n-1)) + average_number_of_loops(n-1)
}
Equivalently:
real average_number_of_loops (int n) {
if (n == 0) {
return 0
} else {
return (1/(2n-1)) + average_number_of_loops(n-1)
}
So I guess I agree with the guy who wrote:
> Summation for i = 1 to N of 1 / 2i – 1. Sorry I can’t figure out how to > resolve.
Except that you have to understand his “1 / 2i – 1” as being “1/ (2i – 1).” Which is no doubt what he intended. But now we have an explanation of why.