AIME 1993 · 第 11 题

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

Simpler Solution 1

Same as solution 1 except that $b_n=1-a_n$. So you don't need that extra calculation for $b_n$.

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} \times \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} \times \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} \times \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} \times \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}$.

Solution 3

Rather than categorizing games as wins or losses, we can categorize them as starters (S), where Alfred starts, and non-starters (NS), where Bonnie starts. Game 1 is a starter, and since Alfred must win Game 6, Game 7 is a non-starter.

As shown in Solution 1, if a player starts a certain game, the probability $P(NS)$ that they will not start the next game (i.e. win the current game) is $\frac{2}{3}$, and the probability $P(S)$ that they will start the next game (i.e. lose the current game) is $\frac{1}{3}$. Similarly, if a player does not start a certain game, $P(NS) = \frac{1}{3}$ and $P(S) = \frac{2}{3}$. We conclude that the probability of switching from S to NS or vice versa is always $\frac{2}{3}$, and the probability of staying the same is always $\frac{1}{3}$.

Listing out all the games from Game 1 to Game 7, we get: S, ?, ?, ?, ?, ?, NS. Between the 7 games, there are 6 opportunities to either switch or stay the same. We need to eventually switch from S to NS, so there must be an odd number of switches. Furthermore, this number is less than 6, so it must be 1, 3, or 5.

1 switch: There are ${6 \choose 1} = 6$ ways to place the switch, so $P = 6\left(\frac{1}{3}\right)^5\left(\frac{2}{3}\right) = \frac{12}{729}$.

3 switches: There are ${6 \choose 3} = 20$ ways to place the switches, so $P = 20\left(\frac{1}{3}\right)^3\left(\frac{2}{3}\right)^3 = \frac{160}{729}$.

5 switches: There are ${6 \choose 5} = 6$ ways to place the switch, so $P = 6\left(\frac{1}{3}\right)\left(\frac{2}{3}\right)^5 = \frac{192}{729}$.

Add up all these probabilities to get $\frac{12+160+192}{729} = \frac{364}{729}$. $364+729=1093$, so the answer is $\boxed{093}$.

Solution 4 (Probability States)

In states problems like this, it is always good to find a relation between the first game and relate it to all other games.

To do such a thing, we first develop a Markov Chain, shown below.

Now, say $A$ is the probability Alfred wins and $B$ is the probability Bonnie wins, given that they each go first. Then, one can notice that $A$ will win either immediately with a chance of $1/2$, or will lose his turn with a chance $1/2$. But then, one can find a bijection that the new case is just the probability Bonnie wins, given that she goes first. However, we want Alfred to win, so the requested probability $A$ is

$$A = \frac{1}{2} + \frac{1}{2}(1-B).$$ Similarly for $B$,

$$B = \frac{1}{2} + \frac{1}{2}(1-A).$$ We can solve for any one of $A$ or $B$, as they both will retain the same probability due to the fact they both start, and we can clearly see that solving for $B$;

$$B = \frac{1}{2} + \frac{1}{2}(1-A) = \frac{1}{2} + \frac{1}{2} - \frac{1}{2}A = 1 - \frac{1}{2}A$$ Substituting the expression for $A$:

$$B = 1 - \frac{1}{2}\left(\frac{1}{2} + \frac{1}{2}(1-B)\right) = 1 - \frac{1}{2}\left(1 - \frac{1}{2}B\right) = 1 - \frac{1}{2} + \frac{1}{4}B = \frac{1}{2} + \frac{1}{4}B$$ in which $B = \frac{1}{2} + \frac{1}{4}B$, or $\frac{3}{4}B = \frac{1}{2}$, or $B = \frac{2}{3}$. Thus, the probability that Alfred wins the first game given he goes first is $2/3$.

Now, let $P_n$ be the probability that on the $n$th game, Alfred wins. One can notice that if Alfred starts, that implies he lost the last game, and thus has a $2/3 (1-P_{n-1})$ chance of winning. However, one can also notice that if Alfred goes second, then he has a $1/3(P_{n-1})$ chance of winning. Thus the recurrence relation

$$P_n = \frac{2}{3} (1-P_{n-1}) + \frac{1}{3}(P_{n-1})$$ is formed.

The recurrence simplifies down to

$$P_n = \frac{2}{3} - \frac{1}{3}(P_{n-1}) \quad : \quad P_1 = \frac{2}{3}.$$ We can bash our way to $P_6$ quite easily (which for the sake of spacing, I will not do). One can also calculate this explicitly, to obtain $P_6 = 364/729$, which is in the form $m/n$, and $m+n = 364+729 = 1093$. The last three digits are $\boxed{093}$.

~Pinotation