Maths Olympiad Prep

Track / Stage 7 / 239 of 300 #1639 of 1964

Problem 1639

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.5 Find the answer

There are 256256 players in a tennis tournament who are ranked from 11 to 256256, with 11 corresponding to the highest rank and 256256 corresponding to the lowest rank. When two players play a match in the tournament, the player whose rank is higher wins the match with probability 35\frac{3}{5}.

In each round of the tournament, the player with the highest rank plays against the player with the second highest rank, the player with the third highest rank plays against the player with the fourth highest rank, and so on. At the end of the round, the players who win proceed to the next round and the players who lose exit the tournament. After eight rounds, there is one player remaining and they are declared the winner.

Determine the expected value of the rank of the winner.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official solution

1. Define the Problem and Notation:
- There are 256 players ranked from 1 to 256.
- The player with the higher rank wins with probability 35\frac{3}{5}.
- We need to determine the expected value of the rank of the winner.

2. Binary Representation and Initial Setup:
- Let an1a_{n-1} be the player with rank nn, where n{1,2,,256}n \in \{1, 2, \ldots, 256\}.
- The binary representation of n1n-1 is b7b6b5b4b3b2b1b0(2)\overline{b_7b_6b_5b_4b_3b_2b_1b_0}_{(2)}, where bi{0,1}b_i \in \{0, 1\} for i{0,1,,7}i \in \{0, 1, \ldots, 7\}.

3. Round 1 Analysis:
- Players A0(2)\overline{A0}_{(2)} and A1(2)\overline{A1}_{(2)} play against each other, where A=b7b6b5b4b3b2b1(2)A = \overline{b_7b_6b_5b_4b_3b_2b_1}_{(2)}.
- A0(2)<A1(2)\overline{A0}_{(2)} < \overline{A1}_{(2)}.
- Probability of A0(2)\overline{A0}_{(2)} winning: 35\frac{3}{5}.
- Probability of A1(2)\overline{A1}_{(2)} winning: 25\frac{2}{5}.
- Probability to win in the first round: p1=2b031b05p_1 = \frac{2^{b_0} \cdot 3^{1-b_0}}{5}.

4. Round 2 Analysis:
- Players B0x(2)\overline{B0x}_{(2)} and B1y(2)\overline{B1y}_{(2)} play against each other, where B=b7b6b5b4b3b2(2)B = \overline{b_7b_6b_5b_4b_3b_2}_{(2)} and x,y{0,1}x, y \in \{0, 1\}.
- B0x(2)<B1y(2)\overline{B0x}_{(2)} < \overline{B1y}_{(2)}.
- Probability of B0x(2)\overline{B0x}_{(2)} winning: 35\frac{3}{5}.
- Probability of B1y(2)\overline{B1y}_{(2)} winning: 25\frac{2}{5}.
- Probability to win in the first two matches: P2(n1)=2b0+b132(b0+b1)52P_2(n-1) = \frac{2^{b_0 + b_1} \cdot 3^{2 - (b_0 + b_1)}}{5^2}.

5. Generalizing for 8 Rounds:
- Probability for player an1a_{n-1} to be the winner:
P8(n1)=2b0+b1++b738(b0+b1++b7)58 P_8(n-1) = \frac{2^{b_0 + b_1 + \cdots + b_7} \cdot 3^{8 - (b_0 + b_1 + \cdots + b_7)}}{5^8}

6. Expected Value Calculation:
- Expected value for n1n-1:
nex1=m=0255m2b0+b1++b738(b0+b1++b7)58 n_{ex} - 1 = \sum_{m=0}^{255} m \cdot \frac{2^{b_0 + b_1 + \cdots + b_7} \cdot 3^{8 - (b_0 + b_1 + \cdots + b_7)}}{5^8}
- Simplifying, we get:
nex1=k=08Sk2k38k58 n_{ex} - 1 = \sum_{k=0}^8 S_k \cdot \frac{2^k \cdot 3^{8-k}}{5^8}
where SkS_k is the sum of numbers mm for which b0+b1++b7=kb_0 + b_1 + \cdots + b_7 = k.

7. **Calculating SkS_k:**
- Number of numbers mm for which b0+b1++b7=kb_0 + b_1 + \cdots + b_7 = k is Nk=(8k)N_k = \binom{8}{k}.
- Sum of these numbers:
Sk=255k(8k)8=255(7k1) S_k = 255 \cdot \frac{k \cdot \binom{8}{k}}{8} = 255 \cdot \binom{7}{k-1}

8. Final Summation:
- Substituting SkS_k:
nex1=k=18255(7k1)2k38k58 n_{ex} - 1 = \sum_{k=1}^8 255 \cdot \binom{7}{k-1} \cdot \frac{2^k \cdot 3^{8-k}}{5^8}
- Simplifying further:
nex1=25525k=07(7k)(25)k(35)7k n_{ex} - 1 = 255 \cdot \frac{2}{5} \cdot \sum_{k=0}^7 \binom{7}{k} \cdot \left(\frac{2}{5}\right)^k \cdot \left(\frac{3}{5}\right)^{7-k}
- Using the binomial theorem:
k=07(7k)(25)k(35)7k=(25+35)7=1 \sum_{k=0}^7 \binom{7}{k} \left(\frac{2}{5}\right)^k \left(\frac{3}{5}\right)^{7-k} = \left(\frac{2}{5} + \frac{3}{5}\right)^7 = 1
- Therefore:
nex1=25525=102 n_{ex} - 1 = 255 \cdot \frac{2}{5} = 102
- Hence, the expected value of the rank of the winner is:
nex=102+1=103 n_{ex} = 102 + 1 = 103

The final answer is 103\boxed{103}

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