2021 JMC 10 Problems/Problem 20

Problem

A particle is in a $5 \times 5$ grid. Each second, it moves to an adjacent cell and when traveling from a cell to another cell, it takes one of the paths with shortest time. The particle starts at cell $A$ and travels to cell $B$ in $3$ seconds, to cell $C$ in $4$ seconds, and finally back to cell $A$ in $5$ seconds. How many possible triples $\{A,B,C\}$ exist?

$\textbf{(A) } 56 \qquad \textbf{(B) }96 \qquad \textbf{(C) } 104 \qquad \textbf{(D) } 136 \qquad \textbf{(E) } 168$

Solution

We do cases on whether $A$ to $B$ is three steps in one direction or two steps in one direction and one step in a perpendicular direction.

Case 1. Three steps straight from $A$ to $B$ .

$[asy] size(4cm); draw((0,0)--(1,0)--(1,4)--(0,4)--cycle); draw((0,1)--(1,1)); draw((0,2)--(1,2)); draw((0,3)--(1,3)); label("${A}$",(0.5,0.5)); label("${B}$",(0.5,3.5)); dot((5.5,0.5),red); dot((4.5,1.5), red); dot((3.5,2.5), purple); dot((2.5,3.5), red); dot((1.5,4.5), red); dot((0.5,5.5), red); dot((-0.5,4.5), red); dot((-1.5,3.5), red); dot((-2.5,2.5), purple); dot((-3.5, 1.5), red); dot((-4.5, 0.5), red); dot((4.5,-0.5), red); dot((3.5,-1.5), red); dot((2.5,-2.5), red); dot((1.5,-3.5), red); dot((0.5,-4.5), red); dot((-0.5,-3.5), red); dot((-1.5,-2.5), red); dot((-2.5,-1.5), red); dot((-3.5,-0.5), red); dot((0.5,-0.5), blue); dot((1.5,0.5), blue); dot((-0.5, 0.5), blue); dot((2.5, 1.5), blue); dot((-1.5, 1.5), blue); dot((4.5, 3.5), blue); dot((-3.5, 3.5), blue); dot((3.5, 4.5), blue); dot((-2.5, 4.5), blue); dot((2.5, 5.5), blue); dot((-1.5, 5.5), blue); dot((1.5, 6.5), blue); dot((-0.5, 6.5), blue); dot((0.5, 7.5), blue); [/asy]$

The red dots mark the places of squares that are 5 away from $A$ and the blue dots mark the squares that are 4 away from $B$ . The two purple dots are valid placements for $C.$ However, we can also have $A$ on top and $B$ on bottom, or $A$ and $B$ aligned horizontally, so we have $4$ symmetries. There are also $2 \cdot 2$ ways to embed the $4\times 4$ hull of $ABC$ into our $5 \times 5$ grid, so our total for this case is $4 \cdot 4 \cdot 2=32$ .

Case 2. Two steps one direction, one step in a perpendicular direction from $A$ to $B$ .

$[asy] size(6cm); draw((0,0)--(2,0)--(2,3)--(0,3)--cycle); draw((1,0)--(1,3)); draw((0,1)--(2,1)); draw((0,2)--(2,2)); label("${A}$",(0.5,0.5)); label("${B}$",(1.5,2.5)); dot((5.5,0.5), red); dot((4.5,1.5), purple); label("($5 \times 3$)",(5,1.5), E); dot((3.5,2.5), red); dot((2.5,3.5), red); dot((1.5,4.5), red); dot((0.5,5.5), purple); label("($2 \times 6$)",(0.2,5.5), NW); dot((-0.5,4.5), purple); label("($3 \times 5$)",(-0.7,4.5), NW); dot((-1.5,3.5), purple); label("($4 \times 4$)",(-1.7,3.5), NW); dot((-2.5,2.5), purple); label("($5 \times 3$)",(-2.7,2.5), NW); dot((-3.5,1.5), red); dot((-4.5,0.5), red); dot((4.5,-0.5), red); dot((3.5,-1.5), red); dot((2.5,-2.5), red); dot((1.5,-3.5), red); dot((0.5,-4.5), red); dot((-0.5,-3.5), red); dot((-1.5,-2.5), red); dot((-2.5,-1.5), red); dot((-3.5,-0.5), red); dot((0.5,-0.5), blue); dot((1.3,-1.5), blue); dot((-0.5,0.5), blue); dot((2.5,-0.5), blue); dot((-1.5,1.5), blue); dot((4.5,3.5), blue); dot((3.5,4.5), blue); dot((2.5,5.5), blue); dot((1.5,6.5), blue); dot((5.5,2.5), blue); dot((3.5,0.5), blue); [/asy]$

We can embed the $2\times6$ hull in $0$ ways (we only have a $5\times5$ grid), a $3\times5$ or $5\times3$ hull in $3$ ways, and a $4\times4$ in $2 \cdot 2=4$ ways. This gives $1 \cdot 0 + 3 \cdot 3 +1 \cdot 4=13$ ways. However, we must multiply this by $8$ to accommodate for the $8$ positions (symmetric) of $B$ relative to $A,$ giving $13 \cdot 2^3 = 104$ cases here. Our final answer is $104+32=136$ .

Page

Toolbox

Search

2021 JMC 10 Problems/Problem 20

Problem

Solution