Problem:
Frieda the frog begins a sequence of hops on a grid of squares, moving one square on each hop and choosing at random the direction of each hop-up, down, left, or right. She does not hop diagonally. When the direction of a hop would take Frieda off the grid, she wraps around and jumps to the opposite edge. For example if Frieda begins in the center square and makes two hops , the first hop would place her in the top row middle square, and the second hop would cause Frieda to jump to the opposite edge, landing in the bottom row middle square. Suppose Frieda starts from the center square, makes at most four hops at random, and stops hopping if she lands on a corner square. What is the probability that she reaches a corner square on one of the four hops?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Let denote the middle square, denote a corner square, and denote an edge square not in the corner. There are four ways to reach a corner in at most four moves starting from :
,
,
,
,
for a total probability of .
The matrices below show the number of ways to reach each square after , and hops.
The first matrix shows that after one hop Frieda will be on one of the side edge squares. There is exactly one way to reach each of those squares in one hop.
The second matrix shows the number of ways to reach each square in two hops. For example to reach the upper left corner, Frieda can come from the right or from below so the two s adjacent to the corner in the first matrix are added to make in the second matrix. It follows that Frieda can reach one of the corner squares in two hops in different ways out of possible two-hop sequences.
Now consider the third hop assuming that a corner square has not yet been reached, making sure to count the wrap-around hops. For example, the top row middle square can be reached from the center square or from the bottom row middle square (but not from the adjacent corner squares). The values and are added from the second matrix to make in the third matrix. The matrix shows that Frieda can reach a corner square on her third hop in different ways out of possible three-hop sequences.
Finally, the fourth matrix shows that Frieda can reach a corner square on her fourth hop in different ways out of possible four-hop sequences. The probability of landing on a corner square on one of the four hops is therefore
The problems on this page are the property of the MAA's American Mathematics Competitions