12. Alberto and Barbara are playing foosball. Before starting, they decide that the game will end as soon as one of them has scored 3 more goals than the other. Knowing that, for each ball played, both Alberto and Barbara have a $50\%$ chance of scoring, what is the probability that the game does not end before the twenty-first goal?
(A) $\frac{3^{9}}{2^{18}}$
(B) $\frac{3^{10}}{2^{20}}$
(C) $\frac{3^{20}}{2^{40}}$
(D) $\frac{13 \cdot 17 \cdot 19 \cdot 31}{2^{18}}$
(E) $\frac{3 \cdot 7 \cdot 13 \cdot 17 \cdot 19}{2^{18}}$

## Numerical answer problems -5 points
12. The answer is (A). Let $P_{n}$ be the probability that the game does not end with the $n$-th goal (nor before). Suppose that after an odd number $(2 k-1)$ of goals the game is not yet over: the difference in the number of goals scored by the two players is then equal to 1 in absolute value, since it is necessarily odd and cannot be greater than 2. Consider the $2 k$-th and the $(2 k+1)$-th goal: the game ends only if both are scored by the player who was already ahead, which happens with probability $1 / 2 \cdot 1 / 2=1 / 4$. With probability $3 / 4$, instead, after the $(2 k+1)$-th goal the goal difference will again be equal to 1, and the game will not be over. We then get $P_{2 k+1}=\frac{3}{4} P_{2 k-1}$, that is, $P_{1}, P_{3}, P_{5}, \ldots$ form a geometric progression with ratio $\frac{3}{4}$. Since clearly $P_{1}=1$ (the game cannot end with the first goal) we have $P_{2 k+1}=(3 / 4)^{k}$ for every $k \geq 0$. The required probability is the probability that at least 21 goals are scored, or equivalently (for parity reasons) that the game does not end with the 19th goal (nor before). The answer is therefore $P_{19}=(3 / 4)^{9}=3^{9} / 2^{18}$.