Difference between revisions of "1993 AIME Problems/Problem 11"

m
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
{{solution}}
+
The probability that the <math>n</math>th flip in each game occurs and is a head is <math>\frac{1}{2^n}</math>. The first person wins if the coin lands heads on an odd numbered flip. So, the probability of the first person winning the game is <math>\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\cdots = \frac{\frac{1}{2}}{1-\frac{1}{4}}=\frac{2}{3}</math>, and the probability of the second person winning is <math>\frac{1}{3}</math>.
 +
 
 +
Let <math>a_n</math> be the probability that Alice wins the <math>n</math>th game, and let <math>b_n</math> be the probability that Bonnie wins the <math>n</math>th game.
 +
 
 +
If Alfred wins the <math>n</math>th game, then the probability that Alfred wins the <math>n+1</math>th game is <math>\frac{1}{3}</math>. If Bonnie wins the <math>n</math>th game, then the probability that Alfred wins the <math>n+1</math>th game is <math>\frac{2}{3}</math>.
 +
 
 +
Thus, <math>a_{n+1}=\frac{1}{3}a_n+\frac{2}{3}b_n</math>.
 +
 
 +
Similarly, <math>b_{n+1}=\frac{2}{3}a_n+\frac{1}{3}b_n</math>.
 +
 
 +
Since Alfred goes first in the <math>1</math>st game, <math>(a_1,b_1)=\left(\frac{2}{3}, \frac{1}{3}\right)</math>.
 +
 
 +
Using these [[recursive]] equations:
 +
 
 +
<math>(a_2,b_2)=\left(\frac{4}{9}, \frac{5}{9}\right)</math>
 +
 
 +
<math>(a_3,b_3)=\left(\frac{14}{27}, \frac{13}{27}\right)</math>
 +
 
 +
<math>(a_4,b_4)=\left(\frac{40}{81}, \frac{41}{81}\right)</math>
 +
 
 +
<math>(a_5,b_5)=\left(\frac{122}{243}, \frac{121}{243}\right)</math>
 +
 
 +
<math>(a_6,b_6)=\left(\frac{364}{729}, \frac{365}{729}\right)</math>
 +
 
 +
Since <math>a_6=\frac{364}{729}</math>, <math>m+n = 1093 \equiv \boxed{093} \pmod{1000}</math>.
  
 
== See also ==
 
== See also ==
 
{{AIME box|year=1993|num-b=10|num-a=12}}
 
{{AIME box|year=1993|num-b=10|num-a=12}}

Revision as of 23:24, 1 July 2008

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 $m/n\,$, where $m\,$ and $n\,$ are relatively prime positive integers. What are the last three digits of $m+n\,$?

Solution

The probability that the $n$th flip in each game occurs and is a head is $\frac{1}{2^n}$. The first person wins if the coin lands heads on an odd numbered flip. So, the probability of the first person winning the game is $\frac{1}{2}+\frac{1}{8}+\frac{1}{32}+\cdots = \frac{\frac{1}{2}}{1-\frac{1}{4}}=\frac{2}{3}$, and the probability of the second person winning is $\frac{1}{3}$.

Let $a_n$ be the probability that Alice wins the $n$th game, and let $b_n$ be the probability that Bonnie wins the $n$th game.

If Alfred wins the $n$th game, then the probability that Alfred wins the $n+1$th game is $\frac{1}{3}$. If Bonnie wins the $n$th game, then the probability that Alfred wins the $n+1$th game is $\frac{2}{3}$.

Thus, $a_{n+1}=\frac{1}{3}a_n+\frac{2}{3}b_n$.

Similarly, $b_{n+1}=\frac{2}{3}a_n+\frac{1}{3}b_n$.

Since Alfred goes first in the $1$st game, $(a_1,b_1)=\left(\frac{2}{3}, \frac{1}{3}\right)$.

Using these recursive equations:

$(a_2,b_2)=\left(\frac{4}{9}, \frac{5}{9}\right)$

$(a_3,b_3)=\left(\frac{14}{27}, \frac{13}{27}\right)$

$(a_4,b_4)=\left(\frac{40}{81}, \frac{41}{81}\right)$

$(a_5,b_5)=\left(\frac{122}{243}, \frac{121}{243}\right)$

$(a_6,b_6)=\left(\frac{364}{729}, \frac{365}{729}\right)$

Since $a_6=\frac{364}{729}$, $m+n = 1093 \equiv \boxed{093} \pmod{1000}$.

See also

1993 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 10
Followed by
Problem 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions