There are $256$ players in a tennis tournament who are ranked from $1$ to $256$, with $1$ corresponding to the highest rank and $256$ 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 $\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.
Problem
Source: Simon Marais Mathematics Competition 2023 Paper B Problem 2
Tags: probability, expected value, combinatorics
23.10.2023 18:55
Denote $a_{n-1}$ the player with the rank $n,\;n\in\{1,2,...,256\}$. $n-1\in\{0,1,2,...,254,255\}$. $255=2^8-1$ and let be $\overline{b_7b_6b_5b_4b_3b_2b_1b_0}_{(2)}$ the binary representation of ${n-1};\;b_i\in\{0,1\}$ for $i\in\{0,1,...,7\}$ (the first digits can be $0$). For example: $38_{(10)}=00100110_{(2)}$. Round 1: A direct match is between the players $\overline{A0}_{(2)}$ and $\overline{A1}_{(2)}$ (the same $A$), where $A=\overline{b_7b_6b_5b_4b_3b_2b_1}_{(2)}$. Occurs the inequality $\overline{A0}_{(2)}<\overline{A1}_{(2)}$. Results: the player $\overline{A0}_{(2)}$ has a probability to win the match $\dfrac{3}{5}$ and the player $\overline{A1}_{(2)}$ has a probability to win the match $\dfrac{2}{5}$. A closed form for the expression of probability to win in the first round: $p_1=\dfrac{2^{b_0}\cdot3^{1-b_0}}{5}$. Round 2: A direct match is between the players $\overline{B0x}_{(2)}$ and $\overline{B1y}_{(2)}$ (the same $B$), where $B=\overline{b_7b_6b_5b_4b_3b_2}_{(2)};\;x,y\in\{0,1\}$. Occurs the inequality $\overline{B0x}_{(2)}<\overline{B1y}_{(2)}$. Results: The player $\overline{B0x}_{(2)}$ has a probability to win the match $\dfrac{3}{5}$ and the player $\overline{B1y}_{(2)}$ has a probability to win the match $\dfrac{2}{5}$, hence the probability is $p_2=\dfrac{2^{b_1}\cdot3^{1-b_1}}{5}$. Results for the player $a_{n-1}$ the probability to win in the first $2$ matches: $P_2(n-1)=\dfrac{2^{b_0+b_1}\cdot3^{2-(b_0+b_1)}}{5^2}$. Repeating the process, results for the player $a_{n-1}$ the probability to be the winner of the tournament: $P_8(n-1)=\dfrac{2^{b_0+b_1+...+b_7}\cdot3^{8-(b_0+b_1+...+b_7)}}{5^8}$. The expected value for $n-1$ is $n_{ex}-1=\sum_{m=0}^{255}m\cdot\dfrac{2^{b_0+b_1+...+b_7}\cdot3^{8-(b_0+b_1+...+b_7)}}{5^8};\;m_{(10)}=\overline{b_7b_6b_5b_4b_3b_2b_1b_0}_{(2)}$. $n_{ex}-1=\sum_{k=0}^8S_k\cdot\dfrac{2^k\cdot3^{8-k}}{5^8}$, where $S_k$ is the sum of the numbers $m$ for witch $b_0+b_1+...+b_7=k$. The number of numbers $m$ for witch $b_0+b_1+...+b_7=k\in\{0,1,2,...,8\}$ (the binary representation of $m$ contains $k$ digits $1$) is: $N_k=\dbinom{8}{k}$. The $N_k$ numbers contain totally $k\cdot\dbinom{8}{k}$ digits $1$. Among the binary representation of the $N_k$ numbers $m$, the digit $1$ appears $\dfrac{k\cdot\dbinom{8}{k}}{8}$ times on each position $b_7,b_6,...,b_1,b_0$. $\overline{11111111}_{(2)}=255_{(10)}$. Results the sum of the numbers $m$ for witch $b_0+b_1+...+b_7=k$: $S_k=255\cdot\dfrac{k\cdot\dbinom{8}{k}}{8}$. For $k=0:\;S_0=0$. For $k\ge1:\;k\cdot\dbinom{8}{k}=k\cdot\dfrac{8!}{k!\cdot(8-k)!}=8\cdot\dfrac{7!}{(k-1)!\cdot[7-(k-1)]!}=$ $=8\cdot\dbinom{7}{k-1}\Longrightarrow S_k=255\cdot\dfrac{8\cdot\dbinom{7}{k-1}}{8}=255\cdot\dbinom{7}{k-1}$. Results: $n_{ex}-1=\sum_{k=0}^8S_k\cdot\dfrac{2^k\cdot3^{8-k}}{5^8}=\sum_{k=1}^8255\cdot\dbinom{7}{k-1}\cdot\dfrac{2^k\cdot3^{8-k}}{5^8}=$ $=255\cdot\dfrac{2}{5}\cdot\sum_{k=0}^7\dbinom{7}{k}\cdot\left(\dfrac{2}{5}\right)^k\cdot\left(\dfrac{3}{5}\right)^{7-k}=102\cdot\left(\dfrac{2}{5}+\dfrac{3}{5}\right)^7=102$. Hence, the expected value of the rank of the winner is $n_{ex}=102+1=103$.