And Then I Blogged Again

So, where did that month go anyway? Well, whatever, I hope the one or two people who still read this have had more than enough time to solve the tying strings problem.

The solution isn't particularly hard:

Consider we have N strings, let f(N) be the solution we seek. Select an end of one of the strings at random (it does not matter which one), and select another end. With 1/(2N-1) probability, they second end is on the same string as the first end, when you tie them together you get 1 loop, plus the problem for f(N-1). With (2N-2)/(2N-1) probability, the second end is on a different string, and when you tie them together you simply have made one string longer and have the f(N-1) case.

So, from this argument, we get the recursion relation for f:

f(N)=1/(2N-1)(f(N-1)+1)+(2N-2)/(2N-1)f(N)
f(N)=f(N-1)+1/(2N-1)

f(1) is 1, of course. f(2) is 1+1/3, f(3) is 1+1/3+1/5. It is a pretty easy thing to prove that:

f(N)=Σ 1/(2k-1)

where k goes from 1 to N.

I guess I'll post the next part of the problem now, in case I forget to blog for the next year:

How long is a loop on average? Specifically, consider one were to select an initial piece of string and ask "what is the expected value of the length of the loop this piece of string will end up in?".