This is what spaghetti looks like

Here’s a nice problem in probability. I like it because at first sight it seems fiercely complicated, but thinking about it in the right way makes it seem much simpler.

You have a bowl filled with *n* strands of spaghetti. You pick two ends from the bowl at random, and tie them together. You keep doing this until there are no more loose ends. Obviously, you will have made some number of loops when you reach the end of this process.

What is the average number of loops created?

### Like this:

Like Loading...

*Related*

## 4 comments

Comments feed for this article

July 21, 2010 at 1:51 pm

archimedesbooksIs it this?

1 + 1/3 + 1/5 + 1/7 + … + 1/(2n-1)

July 21, 2010 at 10:51 pm

Chris TaylorIt is exactly that.

How did you solve it? By creating a recurrence relation for the expectation (my solution) or by some other method?

July 21, 2010 at 10:51 pm

Chris TaylorAnd a related question, I guess, although not nearly so interesting or hard: how does this scale as a function of n?

July 22, 2010 at 12:36 am

archimedesbooksMy logic was this:

We have n strands, so there are 2n ends. Having picked one, the chance of picking the other end of the same strand is 1/(2n-1).

If we *do* pick the other end of the same strand, we’ve made a loop. Otherwise, not. But in either case we reduce the number of unlooped strands by 1 — so after each step with n strands, we have (n-1) strands, and there’s probability 1/(2n-1) that we have a new loop.

We keep tying ends together until we have 0 unlooped strands — this takes n steps. At each step there are k strands, so there’s a probability 1/(2k-1) of forming a new loop. As an interesting aside, for the last step there’s only 1 strand so the probability of forming a loop is 1/(2*1-1) = 1, i.e., the last step necessarily makes a loop.

Hence the expected number of loops is

\sum_{k=1}^n {1 \over 2k-1}

I *think* that’s similar to the recurrence relation you’re thinking of.

As for scaling as a function of n, just off the top of my head I’d say it’s close to the integral of 1/(2n), which will increase logarithmically with n.