Maths Olympiad Prep

Track / Stage 6 / 347 of 400 #1347 of 1964

Problem 1347

National olympiad, first round
Combinatorics Difficulty 6.7 Find the answer

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.

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

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 6×(22)=66 \times \binom{2}{2} = 6 ways to pick two ends from the same rope.
- The total number of ways to pick any two ends from 12 is (122)=12×112=66\binom{12}{2} = \frac{12 \times 11}{2} = 66.
- Therefore, the probability of forming a loop on the first pick is 666=111\frac{6}{66} = \frac{1}{11}.

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 EnE_n be the expected number of loops when starting with nn loose ends.
- Initially, E12E_{12} 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 12k1\frac{1}{2k-1} where kk is the number of pairs of loose ends remaining.
- For n=12n = 12 loose ends, we have 6 pairs, so the expected number of loops is:
E12=k=1612k1 E_{12} = \sum_{k=1}^{6} \frac{1}{2k-1}
- This sum is:
E12=111+19+17+15+13+11 E_{12} = \frac{1}{11} + \frac{1}{9} + \frac{1}{7} + \frac{1}{5} + \frac{1}{3} + \frac{1}{1}

7. Calculating the Sum:
- We calculate each term:
1110.0909,190.1111,170.1429,15=0.2,130.3333,11=1 \frac{1}{11} \approx 0.0909, \quad \frac{1}{9} \approx 0.1111, \quad \frac{1}{7} \approx 0.1429, \quad \frac{1}{5} = 0.2, \quad \frac{1}{3} \approx 0.3333, \quad \frac{1}{1} = 1
- Summing these values:
0.0909+0.1111+0.1429+0.2+0.3333+11.8782 0.0909 + 0.1111 + 0.1429 + 0.2 + 0.3333 + 1 \approx 1.8782

The final answer is 1.878\boxed{1.878}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.