Solved by James Pryor

solution: noodles

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.