George has six ropes. He chooses two of the twelve loose ends at random (possibly
from the same rope), and ties them together, leaving ten loose ends. He again chooses two loose ends at random and joins them, and so on, until there are no loose ends. Find, with proof, the expected value of the number of loops George ends up with.
Problem 1347
Official solution
1. Initial Setup: George starts with 6 ropes, each having 2 loose ends, making a total of 12 loose ends.
2. First Pairing: When George picks two loose ends at random and ties them together, there are two possibilities:
- He ties two ends of the same rope, forming a loop.
- He ties ends from different ropes, reducing the number of ropes by one.
3. Probability of Forming a Loop:
- The probability that the first two ends he picks form a loop is given by the ratio of the number of ways to pick two ends from the same rope to the total number of ways to pick any two ends.
- There are 6 ropes, each with 2 ends, so there are ways to pick two ends from the same rope.
- The total number of ways to pick any two ends from 12 is .
- Therefore, the probability of forming a loop on the first pick is .
4. Subsequent Pairings: After each pairing, the number of loose ends decreases by 2. The process continues until there are no loose ends left. Each time George ties two ends, the probability of forming a loop changes because the number of remaining loose ends changes.
5. Expected Number of Loops:
- Let be the expected number of loops when starting with loose ends.
- Initially, is what we need to find.
- The expected number of loops formed in each step can be calculated by summing the probabilities of forming a loop at each step.
6. Summing the Probabilities:
- The probability of forming a loop at each step is where is the number of pairs of loose ends remaining.
- For loose ends, we have 6 pairs, so the expected number of loops is:
- This sum is:
7. Calculating the Sum:
- We calculate each term:
- Summing these values:
The final answer is .