2020 AMC 10A Problem 13

P11-15~6 minPrint

Conditional Probability & States Paths & Grids Define states/recurrence and iterate Exploit symmetry to reduce work or pair up objects

A frog sitting at the point $(1, 2)$ begins a sequence of jumps, where each jump is parallel to one of the coordinate axes and has length $1$ , and the direction of each jump (up, down, right, or left) is chosen independently at random. The sequence ends when the frog reaches a side of the square with vertices $(0,0), (0,4), (4,4),$ and $(4,0)$ . What is the probability that the sequence of jumps ends on a vertical side of the square?

Show solution without answering

Key insight

The points (1,1), (1,3) and the center sit on diagonals of the square, so from them both kinds of side are equally likely. Look one jump ahead.

Solution

Call a finish on the left or right side a "win". The frog starts at $(1, 2)$ . Instead of following long paths, look at just the first jump and ask: where can the frog land, and what is the chance of a win from there?

1. The first jump. Each direction has chance $\frac14$ .
- Left: lands on $(0, 2)$ , which is on the left side. That is a win right away.
- Right: lands on $(2, 2)$ , the center of the square.
- Up: lands on $(1, 3)$ .
- Down: lands on $(1, 1)$ .
2. The center $(2, 2)$ . From the center the square looks the same in all four directions. Turn the picture a quarter turn and vertical sides become horizontal ones. So a win and a loss are equally likely: the chance is $\frac12$ .
3. The point $(1, 1)$ . It lies on the diagonal from $(0, 0)$ to $(4, 4)$ . Flip the square over that diagonal: $(1,1)$ stays put, every up jump becomes a right jump, and the vertical sides trade places with the horizontal sides. So from $(1, 1)$ , ending on a vertical side is exactly as likely as ending on a horizontal side. The chance is $\frac12$ .
4. The point $(1, 3)$ . It lies on the other diagonal, from $(0, 4)$ to $(4, 0)$ . The same flip argument gives chance $\frac12$ .
5. Put it together. With chance $\frac14$ the frog wins at once. With chance $\frac34$ it lands on a point where its chance is $\frac12$ . So
$\text{chance of a win} = \frac14 \times 1 + \frac34 \times \frac12 = \frac14 + \frac38 = \frac58.$

The answer is $\boxed{\textbf{(B)}\ \frac{5}{8}}$ .

Why this works

For a random walk, the chance from a point is the average of the chances from the points one step away. Symmetry can tell you some of those chances for free: any point on a diagonal of the square sees vertical and horizontal sides the same way. Look for such free values first before writing equations.

Alternative approach

Write equations without the diagonal trick. Let $a$ be the chance from $(1,2)$ , $c$ the chance from $(1,1)$ (the same as from $(1,3)$ by an up-down flip), and $d$ the chance from $(2,1)$ (the same as from $(2,3)$ ). The center is $\frac12$ . Looking one jump ahead from each point:
$a = \tfrac14 + \tfrac14 \cdot \tfrac12 + \tfrac12 c, \qquad c = \tfrac14 + \tfrac14 a + \tfrac14 d, \qquad d = \tfrac14 \cdot \tfrac12 + \tfrac12 c.$
(From $(1,1)$ a down jump loses, left wins; from $(2,1)$ down loses, up goes to the center, left and right go to points like $(1,1)$ .) Solving gives $c = \frac12$ , $d = \frac38$ and $a = \frac58$ .

Concise solution

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

Let $p(x, y)$ be the probability of ending on a vertical side ( $x = 0$ or $x = 4$ ) from the interior point $(x, y)$ . By the square's symmetries, $p(2,2) = \frac12$ (vertical and horizontal look the same from the center), $p(3, y) = p(1, y)$ , and $p(x, 3) = p(x, 1)$ .

Set $a = p(1,2)$ , $c = p(1,1)$ , $d = p(2,1)$ . Conditioning on the first jump:

- From $(1,2)$ : left hits $x = 0$ (win), right goes to $(2,2)$ , up or down goes to a point with value $c$ :
$a = \tfrac14 \cdot 1 + \tfrac14 \cdot \tfrac12 + \tfrac12 c = \tfrac38 + \tfrac12 c.$
- From $(1,1)$ : left wins, down hits $y = 0$ (lose), up goes to $(1,2)$ , right to $(2,1)$ :
$c = \tfrac14 + \tfrac14 a + \tfrac14 d.$
- From $(2,1)$ : down loses, up goes to $(2,2)$ , left or right goes to a point with value $c$ :
$d = \tfrac14 \cdot \tfrac12 + \tfrac12 c = \tfrac18 + \tfrac12 c.$

Substitute $d$ into the second equation: $c = \tfrac14 + \tfrac14 a + \tfrac{1}{32} + \tfrac18 c$ , so $\tfrac78 c = \tfrac{9}{32} + \tfrac14 a$ , i.e. $c = \tfrac{9}{28} + \tfrac{2}{7} a$ .

Then $a = \tfrac38 + \tfrac12\left(\tfrac{9}{28} + \tfrac27 a\right) = \tfrac38 + \tfrac{9}{56} + \tfrac17 a$ , so $\tfrac67 a = \tfrac{21 + 9}{56} = \tfrac{30}{56}$ and $a = \tfrac{30}{56} \cdot \tfrac76 = \tfrac58$ .

The answer is $\boxed{\textbf{(B)}\ \frac{5}{8}}$ .

Review in the AoPS books

Introduction to Counting & Probability, Chapter 8: Basic Probability Techniques (§8.5)
Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
Intermediate Counting & Probability, Chapter 10: Recursion
Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)