Problem 10 · 2016 Math Kangaroo
Easy
Counting & Probability
path-tracingcareful-counting
During a cycle race starting at D and finishing at B, every connecting road between the towns A, B, C and D shown in the diagram is ridden along exactly once. How many possible routes are there for the race?
Show answer
Answer: C — 6
Show hints
Hint 1 of 2
A valid race rides every drawn road exactly once, starting at D and ending at B (an Euler trail).
Still stuck? Show hint 2 →
Hint 2 of 2
List the routes by the first road taken out of D, then trace each to the end at B.
Show solution
Approach: count Euler trails from D to B
- The five roads are A-B, A-D, B-D, B-C and D-C; the race must use each exactly once, leaving D and arriving at B.
- Organise by the first move from D: starting D-A leads to 2 finishing routes, starting D-B leads to 2, and starting D-C leads to 2.
- That makes 2 + 2 + 2 = 6 possible routes.
Mark:
· log in to save