BrainDen.com - Brain Teasers
• 0

# Bored while eating Spaghetti

## Question

You are given a plate of spaghetti and told to do the following: Pick up one end of a spaghetti noodle and tie it to another end of a noodle (randomly selecting each). Continue to do this until all the ends have been tied together. If there were originally N pieces of spaghetti, what is the expected number of loops of spaghetti you would form? A loop may consist of any number of pieces of spaghetti tied together, and the loops could be linked to one another.

## Recommended Posts

• 0

If there are N pieces of spaghetti, the expected number of loops formed is the sum of reciprocals of all odd integers from 1 to 2N-1.

##### Share on other sites

• 0

If there are N pieces of spaghetti, the expected number of loops formed is the sum of reciprocals of all odd integers from 1 to 2N-1.

Wow.

That is thought-provoking.

This is one case for which I am glad the solution details are not (yet) divulged.

Nice puzzle also.

##### Share on other sites

• 0

Consider N strands of spaghetti. Some of these strands may comprise original strands tied end-to-end. Now, it is easy to see that

there are N ways to pick a pair of strand ends which, when tied together would cause a loop to form. Since there are 2NC2 ways
to pick a pair of ends, it follows that the probability of randomly picking ends which would result in a loop is N/2NC2 which
is equal to 1/(2N-1). So, with probability 1/(2N-1), we will form a loop AND decrease the number of strands by 1. With probability 1-(1/(2N-1)),
we will not form a loop but we will decrease the number of strands by 1. Let E(N) be the expected number of loops formed in this way.
Then, E(N) = (1/(2N-1))*(1+E(N-1)) + (1-(1/(2N-1)))*E(N-1) = 1/(2N-1) + E(N-1). Using this recursive formula, we can telescope out to
E(N) = 1/(2N-1) + 1/(2N-3) + ... + E(1). But E(1)=1. So, E(N) = 1/(2N-1) + 1/(2N-3) + ... + 1/1. This says that the expected number of
loops formed is the sum of reciprocals of all odd integers from 1 to 2N-1.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.