A Bowl of Noodles

Discuss all those difficult questions here.

A Bowl of Noodles

Postby BenTheMan » Thu Jul 15, 2010 9:45 pm

I ran across this one, which has had me stumped all day.

Suppose you have a bowl of k noodles. You randomly reach in (with both hands) and extract two noodle ends, then glue them together. You do this k times. What is the expected number of noodle loops ?

There has to be a cute, simple way to do this one, but I haven't been able to come up with anything. I can write down explicit expressions for the case with N = k, N = k-1, N = 2 and N = 1, but they involve !! (double factorials), on account of the fact that one noodle has two ends. It's also true NOT forming a loop is the same as taking one of the noodles out of the bowl. It's hard to see how anything I write down will be analytically soluble.

There's some little trick I'm missing, for sure...
BenTheMan
 
Posts: 38
Joined: Sat May 08, 2010 7:17 pm

Re: A Bowl of Noodles

Postby BenTheMan » Thu Jul 15, 2010 11:39 pm

Ok, that was definitely the wrong way to do it.

I got an answer, but it diverges as k-> \inf (which you expect, surely). It works for the base cases I've checked.

Anyway, you just have to recognize that the number of loops on the nth trial is

N(n) = 1/( 2n - 1 ) + N(n-1).

so

N(k) = 1 + 1/3 + 1/5 + ... + 1/k

which doesn't sum to anything nice, I think.
BenTheMan
 
Posts: 38
Joined: Sat May 08, 2010 7:17 pm

Re: A Bowl of Noodles

Postby blas » Wed Oct 06, 2010 2:54 pm

I think I have found the solution.

First, we must realize that everytime we glue two noodle ends together we either create a closed loop and decrease the number of noodles by one or we just simply decrease the number of noodles by one. Let L(k) be the average number of closed loops created after k choices (one choice is equivalent to glueing the two noodle ends). It is easy to see that:

L(1)=1.

For k=2 we have that

L(2)=2p(1,k)+(1-p(1,k)) L(1),

where p(1,k) is the probability of having created one closed loop out of k=2 noodles. The factor 2 is included because this event can happen k=2 times, the same number of times as noodles there are in the bowl. It can be easily seen that

p(1,k)=1/(2k-1).

Therefore, for k=2:

L(2)=2p(1,k)+1-p(1,k)=1+p(1,k=2)=4/3.

For an arbitrary k, we have that

L(k)=k p(1,k)+(1-p(1,k)) L(k-1).

Now, the problem is to find out a non-recursive representation of L(k). Let's calculate its first few values:

L(1)=1,
L(2)=4/3,
L(3)=5/3,
L(4)=2.

We could deduce form this that:

L(k)=(k+2)/3.

If we input this in the formula for an arbirtrary k+1, we obtain that:

L(k+1)=(k+1) p(1,k+1)+(1-p(1,k+1)) L(k)
=(k+1)/(2k+1) + 2k(k+2)/(3(2k+1))
=(3k+3+2k^2+4k)/(3(2k+1))
=(2k^2+7k+3)/(3(2k+1))
=(2k+1)(k+3)/(3(2k+1))
=(k+3)/3
. q.e.d.

Knowing this, we have solved the problem.
blas
 
Posts: 1
Joined: Wed Oct 06, 2010 12:33 pm

Re: A Bowl of Noodles

Postby bigperm » Mon Dec 20, 2010 11:14 pm

I have a solution that disagrees with blas. I'm not sure about blasses explanation, but Ben, your answer can't be right. Your series isn't well defined unless k is odd. Even in that case, with every round (round=two noodle ends picked) you close off two ends. Since you start with 2k ends you must have k total rounds, but you will have less.

Start with k noodles, so we have 2k noodle ends. Pick any first end and then the chance that your second choice closes a loop is 1/(2k-1). So the expected loops after 1 round (1 round=two end choices) is 1/(2k-1)

For round 2 we are in two different states. Either we have 1 loop and 2(k-1) open ends, or 2(k-1) open ends (one of which is part of a long "double-noodle." In either case, we are back to the same situation as in round 1. So the expected loops made during the second round is 1/(2(k-1) - 1).

Summing all k rounds we see that the denominator takes on all odd values from 1 to 2k-1. So we are summing the numbers 1 + 1/3 + 1/5 + ... + 1/(2k-1).
--BTW, special [; formatting ;] for mathematics is meant to be read with http://thewe.net/tex/
bigperm
 
Posts: 7
Joined: Fri Dec 17, 2010 7:26 am


Return to Interview questions

Who is online

Users browsing this forum: No registered users and 1 guest

cron