Jump to content
BrainDen.com - Brain Teasers
  • 0
BMAD

Bored while eating Spaghetti

Question

BMAD    62

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.

Share this post


Link to post
Share on other sites

3 answers to this question

  • 0
bonanova    76

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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Recently Browsing   0 members

    No registered users viewing this page.

×