Jump to content
BrainDen.com - Brain Teasers
  • 0

Bored while eating Spaghetti


BMAD
 Share

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.

Link to comment
Share on other sites

3 answers to this question

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.

Wow.

That is thought-provoking.

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

Nice puzzle also.

Link to comment
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.
Link to comment
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...