2019 AMC 10B Problem 22

P21-25~7 minPrint

Conditional Probability & States Games & Processes Split into exhaustive cases and handle each Define states/recurrence and iterate

Raashan, Sylvia, and Ted play the following game. Each starts with $\$1$ . A bell rings every $15$ seconds, at which time each of the players who currently have money simultaneously chooses one of the other two players independently and at random and gives $\$1$ to that player. What is the probability that after the bell has rung $2019$ times, each player will have $\$1$ ? (For example, Raashan and Ted may each decide to give $\$1$ to Sylvia, and Sylvia may decide to give her dollar to Ted, at which point Raashan will have $\$0$ , Sylvia will have $\$2$ , and Ted will have $\$1$ , and that is the end of the first round of play. In the second round Raashan has no money to give, but Sylvia and Ted might choose each other to give their $\$1$ to, and the holdings will be the same at the end of the second round.)

Show solution without answering

Key insight

The money is always split 1, 1, 1 or 2, 1, 0 in some order. From either split, the next ring leaves everyone with 1 dollar with probability 1/4.

Solution

$2019$ rounds is far too many to follow. So first ask which situations can even occur, and what happens from each on a single ring.

Step 1: the possible situations.

There is always $\$3$ in total.
Could one player have all $\$3$ ? A player with money must give $\$1$ away, and each of the other two can give at most $\$1$ . If the others each give $\$1$ to one player, that player also gives $\$1$ away, so they end with at most $\$2$ . Nobody ever reaches $\$3$ .
So the money is always split $1, 1, 1$ or $2, 1, 0$ (in some order).

Step 2: from $1, 1, 1$ .

Each of the three players picks one of two others: $2 \cdot 2 \cdot 2 = 8$ equally likely ways.
Everyone keeps $\$1$ only if each player receives exactly one dollar. That happens when the gifts go around in a circle: Raashan to Sylvia to Ted to Raashan, or the reverse. That is $2$ of the $8$ ways.
Probability: $\frac{2}{8} = \frac14$ .

Step 3: from $2, 1, 0$ . Say Raashan has $\$2$ , Sylvia $\$1$ , Ted $\$0$ .

Only Raashan and Sylvia give, each choosing one of two players: $4$ equally likely ways.
To end at $1, 1, 1$ , Raashan must receive nothing and Ted must receive exactly $\$1$ . So Sylvia must give to Ted, and Raashan must give to Sylvia. That is $1$ of the $4$ ways.
Probability: $\frac14$ .

Step 4: conclude. Whatever the situation just before the $2019$ th ring, the chance that ring leaves everyone with $\$1$ is $\frac14$ . So the answer is $\frac14$ .

The answer is $\boxed{\textbf{(B)}\ \frac{1}{4}}$ .

Why this works

A long random process becomes simple when you list its possible situations; here there are only two kinds. Then look at a single step from each one. Because both give the same chance of reaching $1, 1, 1$ , the history before the last ring does not matter, and the number $2019$ is only there to scare you.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The total is always $\$3$ . A player can gain at most $\$2$ in a round and must give away $\$1$ if they have any, so nobody ever reaches $\$3$ . The only possible holdings are $(1,1,1)$ or some arrangement of $(2,1,0)$ .

From $(1,1,1)$ : each of the three players picks one of two recipients, $2^3 = 8$ equally likely outcomes. Everyone ends with $\$1$ exactly when each player receives one dollar, i.e. the gifts form a cycle: $R \to S \to T \to R$ or $R \to T \to S \to R$ . That is $2$ of $8$ , probability $\frac14$ .

From $(2,1,0)$ , say Raashan $2$ , Sylvia $1$ , Ted $0$ : only Raashan and Sylvia give, $2 \cdot 2 = 4$ equally likely outcomes. For everyone to end with $\$1$ , Ted must receive exactly one dollar and Raashan must receive none: Raashan gives to Sylvia and Sylvia gives to Ted. That is $1$ of $4$ , probability $\frac14$ .

So no matter what the holdings are before the final bell, the probability that the $2019$ th ring produces $(1,1,1)$ is $\frac14$ .

The answer is $\boxed{\textbf{(B)}\ \frac{1}{4}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.5)
Intermediate Counting & Probability, Chapter 13: Events With States (§13.4)
Intermediate Counting & Probability, Chapter 10: Recursion
Introduction to Counting & Probability, Chapter 2: Basic Counting Techniques (§2.2)