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"

(→‎Problem)
m (Use asy diagram from Problems page)
 
(26 intermediate revisions by 16 users not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
The one-way routes connecting towns A,M,C,X,Y, and Z are shown in the figure below(not drowns to scale).
+
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?
  
 +
<asy>
 +
/* AMC8 P14 2024, by NUMANA: BUI VAN HIEU */
 +
import graph;
 +
unitsize(2cm);
 +
real r=0.25;
 +
// Define the nodes and their positions
 +
pair[] nodes = { (0,0), (2,0), (1,1), (3,1), (4,0), (6,0) };
 +
string[] labels = { "A", "M", "X", "Y", "C", "Z" };
 +
 +
// Draw the nodes as circles with labels
 +
for(int i = 0; i < nodes.length; ++i) {
 +
    draw(circle(nodes[i], r));
 +
    label("$" + labels[i] + "$", nodes[i]);
 +
}
 +
// Define the edges with their node indices and labels
 +
int[][] edges = { {0, 1}, {0, 2}, {2, 1}, {2, 3}, {1, 3}, {1, 4}, {3, 4}, {4, 5}, {3, 5} };
 +
string[] edgeLabels = { "8", "5", "2", "10", "6", "14", "5", "10", "17" };
 +
pair[] edgeLabelsPos = { S, SE, SW, S, SE, S, SW, S, NE};
 +
// Draw the edges with labels
 +
for (int i = 0; i < edges.length; ++i) {
 +
    pair start = nodes[edges[i][0]];
 +
    pair end = nodes[edges[i][1]];
 +
    draw(start + r*dir(end-start) -- end-r*dir(end-start), Arrow);
 +
    label("$" + edgeLabels[i] + "$", midpoint(start -- end),  edgeLabelsPos[i]);
 +
}
 +
// Draw the curved edge with label
 +
draw(nodes[1]+r * dir(-45)..controls (3, -0.75) and (5, -0.75)..nodes[5]+r * dir(-135), Arrow);
 +
label("$25$", midpoint(nodes[1]..controls (3, -0.75) and (5, -0.75)..nodes[5]), 2S);
 +
</asy>
 +
 +
<math>\textbf{(A)}\ 28 \qquad \textbf{(B)}\ 29 \qquad \textbf{(C)}\ 30 \qquad \textbf{(D)}\ 31 \qquad \textbf{(E)}\ 32</math>
 +
 +
==Note / Warning==
 +
As tempting as it may seem, these diagrams are not drawn to scale. What may visually look like the shortest distance may not be the shortest in terms of the distance shown. I know it may be obvious after some time, but many people are at first lured to path <math>A \rightarrow M \rightarrow C \rightarrow Z</math> just because visually it looks like the shortest distance. This could potentially lead to the incorrect answer <math>\textbf{(E)}\ 32</math>.
 +
 +
~s.khunti
 
==Solution 1==
 
==Solution 1==
 +
 +
We can simply see that path <math>A \rightarrow X \rightarrow M \rightarrow Y \rightarrow C \rightarrow Z</math> will give us the smallest value. Adding, <math>5+2+6+5+10 = \boxed{28}</math>. 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 <math>2</math> ways; <math>A \rightarrow X \rightarrow M</math> (<math>5+2</math>) or <math>A \rightarrow M (8)</math>, so you should take the shorter route (<math>5+2</math>). Another example is M to C, two ways - one is <math>6+5</math> and the other is <math>14</math>. Take the shorter route. After this, you need to consider a few more times - consider if <math>5+10</math> (<math>Y \rightarrow C \rightarrow Z</math>) is greater than <math>17 (Y \rightarrow Z</math>), which it is not, and consider if <math>25 (M \rightarrow Z</math>) is greater than <math>14+10</math> (<math>M \rightarrow C \rightarrow Z</math>) or <math>6+5+10</math> (<math>M \rightarrow Y \rightarrow C \rightarrow Z</math>) which it is not. TLDR: <math>5+2+6+5+10 = \boxed{28}</math>. [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 [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 & 32 \\
 +
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) = \boxed{\textbf{(A) } 28}</math> once the algorithm is complete.
 +
 +
~scrabbler94
 +
 +
 +
==Solution 3 (Variant of Solution 1)==
 +
 +
From <math>A</math>, we want to find the shortest route to <math>Z</math>, so we want to try to find the shortest path through each node (not necessarily all of them). We should follow the arrows, since all of them lead to <math>Z</math>. From <math>A</math>, there are <math>2</math> paths we can take, to <math>M</math> <math>(8)</math>, or to <math>X</math> <math>(5)</math>. We travel to <math>X</math>, since <math>5 < 8</math>. From <math>X</math>, we go to <math>M</math> <math>(2 < 10)</math>, we go to <math>Y</math> <math>6 < 14 < 25</math>, we go to <math>C</math>, <math>(5 < 17)</math> and finally go to <math>Z</math>. Adding up gives <math>5 + 2 + 6 + 5 + 10 = 28 = \boxed{\textbf{(A)}}</math>.
 +
 +
~SpeedCuber7
 +
 +
==Solution 4 (On paper)==
 +
We can cross off a few routes:
 +
*AM can be crossed off because AXM is shorter
 +
*XY can be crossed off because XMY is shorter
 +
*YZ can be crossed off because YCZ is shorter
 +
*MC can be crossed off because MYC is shorter
 +
*MZ can be crossed off because MCZ is shorter
 +
Finally, we are left with a single path AXMYCZ from A to Z which adding it up gives <math>28 = \boxed{\textbf{(A)}}.</math>
 +
 +
==Video Solution (A Clever Explanation You’ll Get Instantly)==
 +
https://youtu.be/5ZIFnqymdDQ?si=2XXS3hZobif8ohhH&t=1553
 +
 +
~hsnacademy
  
 
==Video Solution 1 (easy to digest) by Power Solve==
 
==Video Solution 1 (easy to digest) by Power Solve==
Line 9: Line 90:
 
==Video Solution 2 by SpreadTheMathLove==
 
==Video Solution 2 by SpreadTheMathLove==
 
https://www.youtube.com/watch?v=RRTxlduaDs8
 
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
 +
==Video Solution by Interstigation==
 +
https://youtu.be/ktzijuZtDas&t=1405
 +
 +
==Video Solution by Dr. David==
 +
https://youtu.be/NFYvG_K59rQ
 +
 +
==See Also==
 +
{{AMC8 box|year=2024|num-b=13|num-a=15}}
 +
{{MAA Notice}}

Latest revision as of 01:58, 30 October 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?

[asy] /* AMC8 P14 2024, by NUMANA: BUI VAN HIEU */ import graph; unitsize(2cm); real r=0.25; // Define the nodes and their positions pair[] nodes = { (0,0), (2,0), (1,1), (3,1), (4,0), (6,0) }; string[] labels = { "A", "M", "X", "Y", "C", "Z" }; // Draw the nodes as circles with labels for(int i = 0; i < nodes.length; ++i) { draw(circle(nodes[i], r)); label("$" + labels[i] + "$", nodes[i]); } // Define the edges with their node indices and labels int[][] edges = { {0, 1}, {0, 2}, {2, 1}, {2, 3}, {1, 3}, {1, 4}, {3, 4}, {4, 5}, {3, 5} }; string[] edgeLabels = { "8", "5", "2", "10", "6", "14", "5", "10", "17" }; pair[] edgeLabelsPos = { S, SE, SW, S, SE, S, SW, S, NE}; // Draw the edges with labels for (int i = 0; i < edges.length; ++i) { pair start = nodes[edges[i][0]]; pair end = nodes[edges[i][1]]; draw(start + r*dir(end-start) -- end-r*dir(end-start), Arrow); label("$" + edgeLabels[i] + "$", midpoint(start -- end), edgeLabelsPos[i]); } // Draw the curved edge with label draw(nodes[1]+r * dir(-45)..controls (3, -0.75) and (5, -0.75)..nodes[5]+r * dir(-135), Arrow); label("$25$", midpoint(nodes[1]..controls (3, -0.75) and (5, -0.75)..nodes[5]), 2S); [/asy]

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

Note / Warning

As tempting as it may seem, these diagrams are not drawn to scale. What may visually look like the shortest distance may not be the shortest in terms of the distance shown. I know it may be obvious after some time, but many people are at first lured to path $A \rightarrow M \rightarrow C \rightarrow Z$ just because visually it looks like the shortest distance. This could potentially lead to the incorrect answer $\textbf{(E)}\ 32$.

~s.khunti

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. TLDR: $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 & 32 \\ 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) = \boxed{\textbf{(A) } 28}$ once the algorithm is complete.

~scrabbler94


Solution 3 (Variant of Solution 1)

From $A$, we want to find the shortest route to $Z$, so we want to try to find the shortest path through each node (not necessarily all of them). We should follow the arrows, since all of them lead to $Z$. From $A$, there are $2$ paths we can take, to $M$ $(8)$, or to $X$ $(5)$. We travel to $X$, since $5 < 8$. From $X$, we go to $M$ $(2 < 10)$, we go to $Y$ $6 < 14 < 25$, we go to $C$, $(5 < 17)$ and finally go to $Z$. Adding up gives $5 + 2 + 6 + 5 + 10 = 28 = \boxed{\textbf{(A)}}$.

~SpeedCuber7

Solution 4 (On paper)

We can cross off a few routes:

  • AM can be crossed off because AXM is shorter
  • XY can be crossed off because XMY is shorter
  • YZ can be crossed off because YCZ is shorter
  • MC can be crossed off because MYC is shorter
  • MZ can be crossed off because MCZ is shorter

Finally, we are left with a single path AXMYCZ from A to Z which adding it up gives $28 = \boxed{\textbf{(A)}}.$

Video Solution (A Clever Explanation You’ll Get Instantly)

https://youtu.be/5ZIFnqymdDQ?si=2XXS3hZobif8ohhH&t=1553

~hsnacademy

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

Video Solution by Interstigation

https://youtu.be/ktzijuZtDas&t=1405

Video Solution by Dr. David

https://youtu.be/NFYvG_K59rQ

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=230948"