Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2021 JMC 10 Problems/Problem 20"

(Created page with "==Problem== A particle is in a <math>5 \times 5</math> grid. Each second, it moves to an adjacent cell and when traveling from a cell to another cell, it takes one of the pat...")
 
 
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
 
 
A particle is in a <math>5 \times 5</math> 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 <math>A</math> and travels to cell <math>B</math> in <math>3</math> seconds, to cell <math>C</math> in <math>4</math> seconds, and finally back to cell <math>A</math> in <math>5</math> seconds. How many possible triples <math>\{A,B,C\}</math> exist?
 
A particle is in a <math>5 \times 5</math> 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 <math>A</math> and travels to cell <math>B</math> in <math>3</math> seconds, to cell <math>C</math> in <math>4</math> seconds, and finally back to cell <math>A</math> in <math>5</math> seconds. How many possible triples <math>\{A,B,C\}</math> exist?
  

Latest revision as of 15:49, 1 April 2021

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2021_JMC_10_Problems/Problem_20&oldid=150794"