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=31Pk−1+32(1−Pk−1)=32−31Pk−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