Tying rope ends in a bag

Question

A bag contains 100 ropes, so there are 200 loose ends sticking out. Repeatedly, you reach in and pick two loose ends uniformly at random and tie them together. You keep doing this until no loose ends remain (100 ties total). Each tie may join two different ropes into a longer strand, or join the two ends of the same strand into a closed loop. What is the expected number of loops formed?

Accepted Answer

The answer is \sum{k=1}^{100} \frac{1}{2k-1} \approx \mathbf{3.28} loops. Set up with linearity of expectation. A new loop is created exactly when a tie joins the two ends of the same current strand. So the total number of loops equals the number of ties that "close" a strand. Count the expected number of such closing-ties. Suppose at some step there are 2k loose ends remaining (initially k = 100). You grab one end; then you tie it to another end chosen uniformly from the remaining 2k - 1 ends. Exactly one of those 2k-1 ends is the other end of the same strand, tying to it closes a loop. So: …

Tying rope ends in a bag

Your answer

More Brainteasers questions