Problem 5 · 2017 Math Kangaroo
Easy
Logic & Word Problems
path-tracing
Ten islands are joined by 12 bridges (see the map). Every bridge is open. What is the least number of bridges that must be closed so that it is impossible to travel from island A to island B?
Show answer
Answer: B — 2
Show hints
Hint 1 of 2
You want to cut the fewest bridges so no path of open bridges remains from A to B.
Still stuck? Show hint 2 →
Hint 2 of 2
Look for a bottleneck: the smallest set of bridges whose removal disconnects A from B.
Show solution
Approach: find the minimum cut between A and B
- Closing bridges blocks A from B only when every route between them is broken.
- Search the map for the narrowest bottleneck — the fewest bridges lying on all A–B routes.
- Removing those two bridges cuts every path between A and B, and one bridge is never enough.
- So the minimum is 2 (B).
Mark:
· log in to save