Problem 1248

Solution:

Answer: $\frac{45}{14}$

For each positive integer $n$, let $E_{n}$ denote the expected number of rounds required to determine a winner among $n$ people. Clearly, $E_{1}=0$. When $n=2$, on the first move, there is a $\frac{1}{3}$ probability that there is a tie, and a $\frac{2}{3}$ probability that a winner is determined. In the first case, the expected number of additional rounds needed is exactly $E_{2}$; in the second, it is $E_{1}$. Therefore, we get the relation
$$E_{2}=\frac{1}{3}\left(E_{2}+1\right)+\frac{2}{3}\left(E_{1}+1\right),$$
from which it follows that $E_{2}=\frac{3}{2}$.

Next, if $n=3$, with probability $\frac{1}{9}$ there is only one distinct play among the three players, and with probability $\frac{6}{27}=\frac{2}{9}$ all three players make different plays. In both of these cases, no players are eliminated. In all remaining situations, which occur with total probability $\frac{2}{3}$, two players make one play and the third makes a distinct play; with probability $\frac{1}{3}$ two players are eliminated and with probability $\frac{1}{3}$ one player is eliminated. This gives the relation
$$E_{3}=\frac{1}{3}\left(E_{3}+1\right)+\frac{1}{3}\left(E_{2}+1\right)+\frac{1}{3}\left(E_{1}+1\right),$$
from which we find that $E_{3}=\frac{9}{4}$.

Finally, suppose $n=4$. With probability $\frac{1}{27}$, all four players make the same play, and with probability $\frac{3 \cdot 6 \cdot 2}{81}=\frac{4}{9}$, two players make one play, and the other two players make the other two plays; in both cases no players are eliminated, with total probability $\frac{1}{27}+\frac{4}{9}=\frac{13}{27}$ over the two cases. With probability $\frac{6 \cdot 4}{81}=\frac{8}{27}$, three players make one play and the fourth makes another; thus, there is a probability of $\frac{4}{27}$ for exactly one player being eliminated and a probability of $\frac{4}{27}$ of three players being eliminated.

Then, there is a remaining probability of $\frac{6 \cdot 3}{81}=\frac{2}{9}$, two players make one play and the other two players make another. Similar analysis from before yields
$$E_{4}=\frac{13}{27}\left(E_{4}+1\right)+\frac{4}{27}\left(E_{3}+1\right)+\frac{2}{9}\left(E_{2}+1\right)+\frac{4}{27}\left(E_{1}+1\right)$$
so it follows that $E_{4}=\frac{45}{14}$.