Problem 3 · 2018 Math Kangaroo
Easy
Spatial & Visual Reasoning
path-tracing
The diagram shows the floor plan of Renate's house. Renate enters from the terrace and walks through every door of the house exactly once. Which room does she end up in?
Show answer
Answer: B — 2
Show hints
Hint 1 of 2
Think of each door as an edge and each room as a dot; walking every door once is an Euler trail.
Still stuck? Show hint 2 →
Hint 2 of 2
An Euler trail ends at the other odd-degree room when it starts at an odd-degree one.
Show solution
Approach: model the floor plan as a graph and trace the Euler trail from the terrace
- Treat rooms (and the outside terrace) as vertices and doors as edges.
- Passing through every door exactly once is an Euler trail, which must start and finish at the two rooms with an odd number of doors.
- Starting from the terrace, the trail is forced and ends in room 2.
Mark:
· log in to save