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 "2024 AMC 8 Problems/Problem 14"
(add solution 2)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
The one-way routes connecting towns <math>A,M,C,X,Y,</math> and <math>Z</math> are shown in the figure below(not drawn to scale).The distances in kilometers along each route are marked. Traveling along these routes, what is the shortest distance form A to Z in kilometers?
+
The one-way routes connecting towns <math>A,M,C,X,Y,</math> and <math>Z</math> are shown in the figure below(not drawn to scale).The distances in kilometers along each route are marked. Traveling along these routes, what is the shortest distance from A to Z in kilometers?
  
 
[[File:2024-AMC8-q14.png]]
 
[[File:2024-AMC8-q14.png]]
Line 13: Line 13:
  
 
~MaxyMoosy ~HACKER2022
 
~MaxyMoosy ~HACKER2022
 +
 +
==Solution 2 (Advanced)==
 +
We can execute [https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm Dijkstra's algorithm] by hand to find the shortest path from <math>A</math> to every other town, including <math>Z</math>. This effectively proves that, assuming we execute the algorithm correctly, that we will have found the shortest distance. The distance estimates for each step of the algorithm (from <math>A</math> to each node) are shown below:
 +
 +
<cmath>\begin{array}{|c|c|c|c|c|c|c|} \hline
 +
\text{Current node} & A & M & C & X & Y & Z \\ \hline
 +
A & 0 & 8 & \infty & 5 & \infty & \infty \\
 +
X & 0 & 7 & \infty & 5 & 15 & \infty \\
 +
M & 0 & 7 & 21 & 5 & 13 & 33 \\
 +
Y & 0 & 7 & 18 & 5 & 13 & 30 \\
 +
C & 0 & 7 & 18 & 5 & 13 & 28 \\
 +
Z & 0 & 7 & 18 & 5 & 13 & \textbf{28} \\ \hline
 +
\end{array}</cmath>
 +
The steps are as follows: starting with the initial node <math>A</math>, set <math>d(A)=0</math> and <math>d(v)=\infty</math> for all <math>v \in \{M,C,X,Y,Z\}</math> where <math>d(v)</math> indicates the distance from <math>A</math> to <math>v</math>. Consider the outgoing edges <math>(A,X)</math> and <math>(A,M)</math> and update the distance estimates <math>d(X)=5</math> and <math>d(M)=8</math>, completing the first row of the table.
 +
 +
The node <math>X</math> is the unvisited node with the lowest distance estimate, so we will consider <math>X</math> and its outgoing edges <math>(X,Y)</math> and <math>(X,M)</math>. The distance estimate <math>d(Y)</math> equals <math>d(X)+10=15</math>, and the distance estimate <math>d(M)</math> updates to <math>d(X)+2=7</math>, because <math>7 < 8</math>. This completes the second row of the table. Repeating this process for each unvisited node (in order of its distance estimate) yields the correct distance <math>d(Z) = 28</math> once the algorithm is complete.
  
 
==Video Solution 1 (easy to digest) by Power Solve==
 
==Video Solution 1 (easy to digest) by Power Solve==

Revision as of 14:28, 31 January 2024

Problem

The one-way routes connecting towns $A,M,C,X,Y,$ and $Z$ are shown in the figure below(not drawn to scale).The distances in kilometers along each route are marked. Traveling along these routes, what is the shortest distance from A to Z in kilometers?

2024-AMC8-q14.png

$\textbf{(A)}\ 28 \qquad \textbf{(B)}\ 29 \qquad \textbf{(C)}\ 30 \qquad \textbf{(D)}\ 31 \qquad \textbf{(E)}\ 32$

Solution 1

We can simply see that path $A \rightarrow X \rightarrow M \rightarrow Y \rightarrow C \rightarrow Z$ will give us the smallest value. Adding, $5+2+6+5+10 = \boxed{28}$. This is nice as it’s also the smallest value, solidifying our answer.

You can also simply brute-force it or sort of think ahead - for example, getting from A to M can be done $2$ ways; $A \rightarrow X \rightarrow M$ ($5+2$) or $A \rightarrow M (8)$, so you should take the shorter route ($5+2$). Another example is M to C, two ways - one is $6+5$ and the other is $14$. Take the shorter route. After this, you need to consider a few more times - consider if $5+10$ ($Y \rightarrow C \rightarrow Z$) is greater than $17 (Y \rightarrow Z$), which it is not, and consider if $25 (M \rightarrow Z$) is greater than $14+10$ ($M \rightarrow C \rightarrow Z$) or $6+5+10$ ($M \rightarrow Y \rightarrow C \rightarrow Z$) which it is not. TL;DR: $5+2=6=5=10 = \boxed{28}$. [Note: This is probably just the thinking behind the solution.] {Double-note: As MaxyMoosy said, since this answer is the smallest one, it has to be the right answer.}

~MaxyMoosy ~HACKER2022

Solution 2 (Advanced)

We can execute Dijkstra's algorithm by hand to find the shortest path from $A$ to every other town, including $Z$. This effectively proves that, assuming we execute the algorithm correctly, that we will have found the shortest distance. The distance estimates for each step of the algorithm (from $A$ to each node) are shown below:

\[\begin{array}{|c|c|c|c|c|c|c|} \hline \text{Current node} & A & M & C & X & Y & Z \\ \hline A & 0 & 8 & \infty & 5 & \infty & \infty \\ X & 0 & 7 & \infty & 5 & 15 & \infty \\ M & 0 & 7 & 21 & 5 & 13 & 33 \\ Y & 0 & 7 & 18 & 5 & 13 & 30 \\ C & 0 & 7 & 18 & 5 & 13 & 28 \\ Z & 0 & 7 & 18 & 5 & 13 & \textbf{28} \\ \hline \end{array}\] The steps are as follows: starting with the initial node $A$, set $d(A)=0$ and $d(v)=\infty$ for all $v \in \{M,C,X,Y,Z\}$ where $d(v)$ indicates the distance from $A$ to $v$. Consider the outgoing edges $(A,X)$ and $(A,M)$ and update the distance estimates $d(X)=5$ and $d(M)=8$, completing the first row of the table.

The node $X$ is the unvisited node with the lowest distance estimate, so we will consider $X$ and its outgoing edges $(X,Y)$ and $(X,M)$. The distance estimate $d(Y)$ equals $d(X)+10=15$, and the distance estimate $d(M)$ updates to $d(X)+2=7$, because $7 < 8$. This completes the second row of the table. Repeating this process for each unvisited node (in order of its distance estimate) yields the correct distance $d(Z) = 28$ once the algorithm is complete.

Video Solution 1 (easy to digest) by Power Solve

https://youtu.be/2AVrraozwF8

Video Solution 2 by SpreadTheMathLove

https://www.youtube.com/watch?v=RRTxlduaDs8

Video Solution 3 by NiuniuMaths (Easy to understand!)

https://www.youtube.com/watch?v=V-xN8Njd_Lc

~NiuniuMaths

Video Solution by CosineMethod [🔥Fast and Easy🔥]

https://www.youtube.com/watch?v=bAxLRYT6SCw

Video Solution by Math-X (First fully understand the problem!!!)

https://youtu.be/BaE00H2SHQM?si=y_YVZFC4DQdB2qhM&t=3280

~Math-X

See Also

2024 AMC 8 (Problems • Answer Key • Resources)
Preceded by
Problem 13 		Followed by
Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AJHSME/AMC 8 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AMC_8_Problems/Problem_14&oldid=213953"