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 , where and are relatively prime positive integers. What are the last three digits of ?
This problem is copyrighted by the American Mathematics Competitions.
Instructions for entering answers:
For questions or comments, please email firstname.lastname@example.org.