All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Shoelaces (Posted on 2005-04-05) Difficulty: 3 of 5
You have a drawer with n shoelaces in it. You reach into the drawer and select two lace ends at random, and tie them together. Repeat this until there are no more untied lace ends left.

If the two ends are from the same lace, or from the same group of laces already tied at their ends, it will form a loop, and therefore no longer have any free ends.

Continue this until all laces are parts of loops, of either 1 lace, 2 laces, etc.

When you're finished, a certain number of loops will have been formed in this fashion, consisting of one or more laces.

What is the expected number of loops?

See The Solution Submitted by Charlie    
Rating: 3.8333 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts re: Recursive definition | Comment 3 of 7 |
(In reply to Recursive definition by Jer)

As noted in an earlier comment, this problem lends itself to a solution by recursive methods.  Jer has shown that the expected number of loops is given by the equations

E(1) = 1
E(n) = E(n-1)*(2n-2)/(2n-1) + (E(n-1)+1)*1/(2n-1)

It is possible to simplify the second of these equations:

E(n) = E(n-1)*(2n-2)/(2n-1) + E(n-1)*1/(2n-1) + 1/(2n-1)

= E(n-1)[(2n-2)/(2n-1) + 1/(2n-1)] + 1/(2n-1)

= E(n-1)[(2n-2+1)/(2n-1)] + 1/(2n-1)

= E(n-1)[(2n-1)/(2n-1)] + 1/(2n-1)

=E(n-1) + 1/(2n-1)

So, we can define the expected number of loops recursively with the two equations

E(1) = 1
E(n) = E(n-1) + 1/(2n-1)

Again, this gives us the solution of 1 + 1/3 + 1/5 + ... + 1/(2n-1)

-John


  Posted by John Reid on 2005-04-05 20:00:28
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information