Problem 16 · 2022 Math Kangaroo
Hard
Logic & Word Problems
careful-counting
The diagram shows a map with 16 towns which are connected via roads. The government is planning to build power plants in some towns. Each power plant can generate enough electricity for the town in which it stands as well as for its immediate neighbouring towns (i.e. towns that can be reached via a direct connecting road). What is the minimum number of power plants that have to be built?
Show answer
Answer: B — 4
Show hints
Hint 1 of 2
Each plant covers its own town plus every town directly joined to it.
Still stuck? Show hint 2 →
Hint 2 of 2
Find the fewest towns whose coverage reaches all 16 (a dominating set).
Show solution
Approach: minimum dominating set (deferred to key)
- You need a set of towns so that every town is chosen or adjacent to a chosen one.
- Placing plants well, four towns suffice to cover all sixteen, and three cannot.
- Minimum number of plants = 4.
Mark:
· log in to save