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)
(→‎Solution 2)
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 ==
+
==Solution 2 (Kind of Bashy) ==
 
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>
  
 
From this, we can see that Alfred’s (who goes first) chance of winning the first round is:
 
From this, we can see that Alfred’s (who goes first) chance of winning the first round is:
  
−
  <math>\frac{1}{2}</math> + <math>\frac{1}{8}</math> + <math>\frac{1}{32}</math> + \cdots = <math>\frac{2}{3}</math>.
+
  <math>\frac{1}{2}</math> + <math>\frac{1}{8}</math> + <math>\frac{1}{32}</math> + . . . = <math>\frac{2}{3}</math>.
  
 
Bonnie’s (who goes second) chance of winning the first round is then 1 - <math>\frac{2}{3}</math> = <math>\frac{1}{3}</math>.
 
Bonnie’s (who goes second) chance of winning the first round is then 1 - <math>\frac{2}{3}</math> = <math>\frac{1}{3}</math>.
Line 48: Line 48:
 
Adding up the cases, we get <math>\frac{2}{9}</math> + <math>\frac{2}{9}</math> = <math>\frac{4}{9}</math>.
 
Adding up the cases, we get <math>\frac{2}{9}</math> + <math>\frac{2}{9}</math> = <math>\frac{4}{9}</math>.
  
−
Alfred, therefore, has a <math>\frac{4}{9}</math> of winnning the second round, and Bonnie has a 1- <math>\frac{5}{9}</math> of winning this round.
+
Alfred, therefore, has a <math>\frac{4}{9}</math> of winnning the second round, and Bonnie has a 1- <math>\frac{4}{9}</math> = <math>\frac{5}{9}</math> chance of winning this round.
 +
 
 +
From here, it is not difficult to see that the probabilities alternate in a pattern. Set A as the probability that Alfred wins a round.
 +
 
 +
The chances of winning for the first round are A and A - <math>\frac{1}{3}</math>, which can be written as 2A - <math>\frac{1}{3}</math> = 1
 +
 
 +
The second round’s chances are A and A + <math>\frac{1}{9}</math>, which can also be written as 2A + <math>\frac{1}{9}</math>
 +
 
 +
From this, we can conclude that for the <math>n</math>th even round, the probability that Alfred (A) wins can be calculated through the equation 2A + <math>\frac{1}{3^n}</math>.
 +
 
 +
Solving the equation for <math>n</math> = 6, we get A_6 = <math>\frac{364}{729}</math>.
 +
 
 +
364 + 729 = 1093, and the last three digits of this answer is <math>\boxed{093}</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}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 17:34, 25 February 2018

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)

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}$ + . . . = $\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. Set A as the probability that Alfred wins a round.

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

The second round’s 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}$.

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

364 + 729 = 1093, and the last three digits of this 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=92358"