Problem:
Alfred and Bonnie play a game in which they take turns tossing a fair coin. The winner of a game is the first person to obtain a head. Alfred and Bonnie play this game several times with the stipulation that the loser of a game goes first in the next game. Suppose that Alfred goes first in the first game, and that the probability that he wins the sixth game is nm​, where m and n are relatively prime positive integers. What are the last three digits of m+n?
Solution:
For any game the probability that the first player wins the game is
21​+(21​)3+(21​)5+⋯=1−(21​)221​​=32​
Hence the probability that the second player wins the game is 1−32​=31​. Now let Pk​ denote the probability that Alfred wins the kth game. Then P1​=32​ and for k≥2 we have
Pk​=31​Pk−1​+32​(1−Pk−1​)=32​−31​Pk−1​
from which
Pk​−21​=−31​(Pk−1​−21​).
It follows that
Pk​=21​+3k−1(−1)k−1​(P1​−21​)=21​+2⋅3k(−1)k−1​
When k=6, this probability is 729364​. Then m+n=1093 and the last three digits are 093​.
The problems on this page are the property of the MAA's American Mathematics Competitions