Rados Radoicic wrote me:
“Several years back, I heard the following puzzle that turns out to be rather ‘classical’:
“There are N ropes in a bag. In each step, two rope ends are picked uniformly at random, tied together and put back into a bag. The process is repeated until there are no free ends. What is the expected number of loops at the end of the process?”
Before moving on, please try to answer this question.
Let me go on with Rados’ email:
“Upon hearing this puzzle, I came up with and have been wondering (for years now) about the following “natural” variation:
“What if at each step, each end is picked with the probability proportional to the length of its rope?”
I made no epsilon-worthy progress on this problem since then. A properly-trained probabilist (unlike me) might find it easy, but somehow my gut feeling tells me it may be very interesting and not simple at all.”
The challenges are to test yourself on the first question and try to answer the second. No polls this time; comments and thoughts on both versions are welcome.