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 in the tournament and they are declared the winner.

Determine the expected value of the rank of the winner.
More generally, suppose that there are $2^{n}$ players, so that the tournament lasts for $n$ rounds. Furthermore, suppose that the person whose rank is higher wins the match with probability $p$. Let $W$ be the random variable corresponding to the rank of the winner. We will prove by induction that for every positive integer $n$, the expected value is
$$
E[W]=2^{n}-2^{n} p+p .
$$

In the case $n=1$, the tournament consists of only one match and we have
$$
E[W]=1 \times P(X=1)+2 \times P(X=2)=1 \times p+2 \times(1-p)=2-p .
$$

Therefore, the claim is true for $n=1$.
Now assume that the claim is true for some positive integer $n$ and consider a tournament with $2^{n+1}$ players. One can consider the top half of the draw as a tournament with $2^{n}$ players that produces the finalist with the higher rank and the bottom half of the draw as a tournament with $2^{n}$ players that produces the finalist with the lower rank. Let $W_{+}$ be the random variable corresponding to the rank of the finalist from the top half of the draw and let $W_{-}$be the random variable corresponding to the rank of the finalist from the bottom half of the draw. Then we have $E\left[W_{-}\right]=E\left[W_{+}\right]+2^{n}$ and $E\left[W_{+}\right]=2^{n}-2^{n} p+p$ by the induction hypothesis. Therefore,
$$
\begin{aligned}
E[W] & =p \times E\left[W_{+}\right]+(1-p) \times E\left[W_{-}\right] \\
& =p \times\left(2^{n}-2^{n} p+p\right)+(1-p) \times\left(2^{n}-2^{n} p+p+2^{n}\right) \\
& =2^{n}-2^{n} p+p+2^{n}-2^{n} p \\
& =2^{n+1}-2^{n+1} p+p .
\end{aligned}
$$

Thus, the claim is true for a tournament with $2^{n+1}$ players. By induction, we have proven the claim for a tournament with $2^{n}$ players for every positive integer $n$.

Finally, the statement of the problem uses $n=8$ and $p=\frac{3}{5}$, in which case the expected value of the rank of the winner is
$$
2^{8}-2^{8} \times \frac{3}{5}+\frac{3}{5}=103 .
$$

Solution 2
More generally, suppose that there are $2^{n}$ players, so that the tournament lasts for $n$ rounds. Furthermore, suppose that the person whose rank is higher wins the match with probability $p$. Let $W$ be the random variable corresponding to the rank of the winner. We will prove that
$$
E[W]=2^{n}-2^{n} p+p .
$$

Consider the player whose rank is $k$ and the probability with which they win the tournament. Express the integer $k-1$ in binary, but pad it out with preceding 0 s to create a binary string of length $n$. Observe that in round $r$, this player plays someone with higher rank if the $r$ th last binary digit of the string is 1 ; similarly, they play someone with lower rank if the $r$ th last binary digit of the string is 0 .

So the probability that the player whose rank is $k$ wins the tournament is equal to $p^{n-b(k-1)}(1-p)^{b(k-1)}$, where $b(k-1)$ represents the number of times that a 1 appears in the binary representation of $k-1$. The quantity that we would like to calculate is
$$
\begin{aligned}
E[W] & =\sum_{k=1}^{2^{n}} k \times p^{n-b(k-1)}(1-p)^{b(k-1)} \\
& =\sum_{k=0}^{2^{n}-1}(k+1) \times p^{n-b(k)}(1-p)^{b(k)} \\
& =\sum_{b=0}^{n} \sum_{k: b(k)=b}(k+1) p^{n-b}(1-p)^{b} \\
& =\sum_{b=0}^{n} p^{n-b}(1-p)^{b} \sum_{k: b(k)=b}(k+1) .
\end{aligned}
$$

The inner summation is simply the sum of all the non-negative integers whose binary representation contains at most $n$ digits, precisely $k$ of which are 1 . There are exactly $\binom{n}{k}$ such integers and in total, there are $k\binom{n}{k}$ times that 1 appears as a binary digit amongst these integers. So by symmetry, 1 appears as the $m$ th binary digit from the right $\frac{k}{n}\binom{n}{k}$ times for each $m=1,2, \ldots, n$. It then follows that we have
$$
\sum_{k: b(k)=b} b=\frac{b}{n}\binom{n}{b} \times\left(2^{0}+2^{1}+2^{2}+\cdots+2^{n-1}\right)=\frac{b}{n}\binom{n}{b} \times\left(2^{n}-1\right) .
$$

Substituting this into the expression above, we obtain that the expected value of the winner's rank is
$$
\begin{aligned}
& \sum_{b=0}^{n} p^{n-b}(1-p)^{b} \frac{b}{n}\binom{n}{b} \times\left(2^{n}-1\right)+1 \\
= & \frac{2^{n}-1}{n} \sum_{b=0}^{n} p^{n-b}(1-p)^{b} b\binom{n}{b}+1 \\
= & \frac{2^{n}-1}{n}\left[x \frac{\partial}{\partial x} \sum_{b=0}^{n} y^{n-b} x^{b}\binom{n}{b}\right]_{x=1-p, y=p}+1 \\
= & \frac{2^{n}-1}{n}\left[x \frac{\partial}{\partial x}(x+y)^{n}\right]_{x=1-p, y=p}+1 \\
= & \frac{2^{n}-1}{n}\left[n x(x+y)^{n-1}\right]_{x=1-p, y=p}+1 \\
= & \left(2^{n}-1\right)(1-p)+1 \\
= & 2^{n}-2^{n} p+p .
\end{aligned}
$$

Finally, the statement of the problem uses $n=8$ and $p=\frac{3}{5}$, in which case the expected value of the rank of the winner is
$$
2^{8}-2^{8} \times \frac{3}{5}+\frac{3}{5}=103 .
$$