Problem 10 · AMC 8 Stretch
Stretch
Logic & Word Problems
Counting & Probability
visual-representationlogical-reasoning
A building project has stages \(P_1, \dots, P_6\) (\(P_1\) start, \(P_6\) finish). An arrow '\(P_2 \to P_5 = 9\)' means \(P_2\) must finish before \(P_5\) and that step takes 9 days. The steps (in days): \(P_1\to P_2 = 4\), \(P_2\to P_3 = 6\), \(P_2\to P_5 = 9\), \(P_2\to P_4 = 8\), \(P_3\to P_5 = 7\), \(P_5\to P_6 = 3\), \(P_4\to P_6 = 6\). What is the shortest total time to finish the whole project (in days)?
Show answer
Answer: 20 days
Show hints
Hint 1 of 4
Draw the stages as dots and each step as an arrow with its days. Steps that don't depend on each other can happen at the same time.
Still stuck? Show hint 2 →
Hint 2 of 4
Surprise: the project isn't done until EVERY chain of steps is done. So the finish time is set by the LONGEST chain from start to finish.
Still stuck? Show hint 3 →
Hint 3 of 4
List every path of arrows from \(P_1\) to \(P_6\) and add up the days along each one.
Show solution
Approach: Longest path (critical path) in the activity network
- Steps on different branches run at the same time, so the project finishes only when the longest must-do-in-order chain is complete.
- List the paths from \(P_1\) to \(P_6\): \(P_1\to P_2\to P_3\to P_5\to P_6 = 4+6+7+3 = 20\); \(P_1\to P_2\to P_5\to P_6 = 4+9+3 = 16\); \(P_1\to P_2\to P_4\to P_6 = 4+8+6 = 18\).
- The longest is 20 days, along \(P_1\to P_2\to P_3\to P_5\to P_6\), which is the bottleneck (critical path).
- So the whole project needs 20 days; the other branches finish within that time.
Mark:
· log in to save