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?
(In reply to re(2): Recursive definition
Af first it seems a bit counterintuitive (at least to me) that one
expects 1.7 loops for 4 shoelaces, while for 100 shoelaces one only
expects 3.2 loops.
But seeing that you are all right I have rethought my initial impression.
So "revising my intuitive thought" I would say that while it is
true that the more shoelaces there are there is more potential for
loops to be created, it is more difficult to actually close them since
you need to grab a particular opposite end from the many ends you can
Both effects kind of cancel out leaving the tiny
logaritmic growth of the number of expected loops with the number of
Edited on April 6, 2005, 7:22 pm
Posted by ajosin
on 2005-04-06 19:21:10