Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution 2 (Kind of Bashy))
(→‎Solution 2 (Kind of Bashy but very noice))
Line 29: Line 29:
 
Since <math>a_6=\frac{364}{729}</math>, <math>m+n = 1093 \equiv \boxed{093} \pmod{1000}</math>.
 
Since <math>a_6=\frac{364}{729}</math>, <math>m+n = 1093 \equiv \boxed{093} \pmod{1000}</math>.
  
−
==Solution 2 (Kind of Bashy but very noice) ==
+
==Solution 2 (Kind of Bashy but very nice) ==
 
In order to begin this problem, we need to calculate the probability that Alfred will win on the first round. Because he goes first, Alfred has a <math>\frac{1}{2}</math> chance of winning (getting heads) on his first flip. Then, Bonnie, who goes second, has a <math>\frac{1}{2}</math> * <math>\frac{1}{2}</math> = <math>\frac{1}{4}</math>, chance of winning on her first coin toss. Therefore Alfred’s chance of winning on his second flip is <math>\frac{1}{4}</math> * <math>\frac{1}{2}</math> = <math>\frac{1}{8}</math>
 
In order to begin this problem, we need to calculate the probability that Alfred will win on the first round. Because he goes first, Alfred has a <math>\frac{1}{2}</math> chance of winning (getting heads) on his first flip. Then, Bonnie, who goes second, has a <math>\frac{1}{2}</math> * <math>\frac{1}{2}</math> = <math>\frac{1}{4}</math>, chance of winning on her first coin toss. Therefore Alfred’s chance of winning on his second flip is <math>\frac{1}{4}</math> * <math>\frac{1}{2}</math> = <math>\frac{1}{8}</math>
  

Revision as of 05:58, 19 August 2020

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 Alfred 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}$.

Solution 2 (Kind of Bashy but very nice)

In order to begin this problem, we need to calculate the probability that Alfred will win on the first round. Because he goes first, Alfred has a $\frac{1}{2}$ chance of winning (getting heads) on his first flip. Then, Bonnie, who goes second, has a $\frac{1}{2}$ * $\frac{1}{2}$ = $\frac{1}{4}$, chance of winning on her first coin toss. Therefore Alfred’s chance of winning on his second flip is $\frac{1}{4}$ * $\frac{1}{2}$ = $\frac{1}{8}$

From this, we can see that Alfred’s (who goes first) chance of winning the first round is:

\[\frac{1}{2} + \frac{1}{8} + \frac{1}{32} + \cdots = \frac{2}{3}\]

Bonnie’s (who goes second) chance of winning the first round is then 1 - $\frac{2}{3}$ = $\frac{1}{3}$.

This means that the person who goes first has a $\frac{2}{3}$ chance of winning the round, while the person who goes second has a $\frac{1}{3}$ chance of winning.

Now, through casework, we can calculate Alfred’s chance of winning the second round.

Case 1: Alfred wins twice; $\frac{2}{3}$ * $\frac{1}{3}$ (Bonnie goes first this round) = $\frac{2}{9}$.

Case 2: Alfred loses the first round, but wins the second; $\frac{1}{3}$ * $\frac{2}{3}$ = $\frac{2}{9}$.

Adding up the cases, we get $\frac{2}{9}$ + $\frac{2}{9}$ = $\frac{4}{9}$.

Alfred, therefore, has a $\frac{4}{9}$ of winnning the second round, and Bonnie has a 1- $\frac{4}{9}$ = $\frac{5}{9}$ chance of winning this round.

From here, it is not difficult to see that the probabilities alternate in a pattern. Make A the probability that Alfred wins a round.

The chances of Alfred and Bonnie, respectively, winning the first round are A and A - $\frac{1}{3}$, which can be written as 2A - $\frac{1}{3}$ = 1

The second round’s for chances are A and A + $\frac{1}{9}$, which can also be written as 2A + $\frac{1}{9}$

From this, we can conclude that for the $n$th even round, the probability that Alfred (A) wins can be calculated through the equation 2A + $\frac{1}{3^n} = 1$.

Solving the equation for $n$ = 6, we get A = $\frac{364}{729}$.

364 + 729 = 1093, so our answer is $\boxed{093}$.

See also

1993 AIME (Problems • Answer Key • Resources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1993_AIME_Problems/Problem_11&oldid=132141"