• 0

Bored while eating Spaghetti

Question

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites

3 answers to this question

  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.
0

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.