Problem 10 · 2018 Math Kangaroo
Medium
Logic & Word Problems
careful-counting
In the diagram the circles are light bulbs, joined by lines to some other light bulbs. At the start every bulb is switched off. If you touch a bulb, then that bulb and all the bulbs directly joined to it switch on. What is the smallest number of bulbs you have to touch in order to switch on all the bulbs?
Show answer
Answer: A — 2
Show hints
Hint 1 of 2
Touching one bulb lights it and every bulb directly joined to it, so look for a bulb connected to many others.
Still stuck? Show hint 2 →
Hint 2 of 2
Find the fewest bulbs whose neighbourhoods together cover all of them - two well-placed touches are enough here.
Show solution
Approach: dominating set - cover all bulbs with fewest touches
- Touching a bulb switches on that bulb and all bulbs joined to it by an edge.
- Look for bulbs whose connections together reach every bulb in the picture.
- Two suitably chosen bulbs cover the whole network, and one is not enough.
- The minimum is 2.
Mark:
· log in to save