Problem 5 · 2024 Math Kangaroo
Medium
Spatial & Visual Reasoning
path-tracing
Tim wants to draw the figure shown without lifting his pencil off the paper, so he has to go over some parts more than once. The segment lengths are marked on the figure. If he may choose his starting point freely, what is the shortest total length of line he draws?
Show answer
Answer: B — 15 cm
Show hints
Hint 1 of 2
A figure can be drawn in one stroke only if it has zero or two odd-degree vertices.
Still stuck? Show hint 2 →
Hint 2 of 2
Each odd vertex beyond the allowed two forces you to retrace one extra edge; retrace the shortest ones.
Show solution
Approach: Euler path: keep only two odd vertices, retrace the shortest edges
- A figure can be drawn in one stroke only if it has at most two vertices where an odd number of segments meet; you may start and end at those two.
- This figure has more than two odd vertices, so the extra odd vertices must be paired up by re-drawing (retracing) a path between them, and you pick the shortest segments to repeat.
- Adding the length of the whole figure to those shortest retraced pieces gives the minimum stroke length of 15 cm, answer B.
Mark:
· log in to save