Problem 3 · 2017 Math Kangaroo
Medium
Logic & Word Problems
path-tracing
In the diagram we see 10 islands that are connected by 15 bridges. What is the minimum number of bridges that need to be closed off so that there is no longer any connection from A to B?
Show answer
Answer: C — 3
Show hints
Hint 1 of 2
You want the fewest bridges whose removal leaves no path at all from A to B.
Still stuck? Show hint 2 →
Hint 2 of 2
Look for a bottleneck: the smallest set of bridges that every A-to-B route must use.
Show solution
Approach: find a minimum cut (smallest bottleneck of bridges) separating A from B
- Every route from A to B has to cross a narrow set of bridges.
- Trace the routes and find the smallest group of bridges that all of them share.
- Removing that bottleneck of 3 bridges disconnects A from B, and no smaller set works.
Mark:
· log in to save