Consider an art gallery whose walkways are shown as lines in the diagram. A black dot represents a junction of two walkways. A guard may be placed at a junction to watch over the walkways that join at that junction. The minimum number of guards needed to watch all the walkways is ________.
Show Hint
Each junction touches 2 walkways, so count how many walkways a guard can cover, then find the fewest junctions that together cover all 5 walkways.
Step 1: Understanding the Question.
The diagram has 5 junctions (dots) joined by 5 walkways (lines), forming a closed loop: the top junction connects to the two middle junctions, each middle junction connects down to one bottom junction, and the two bottom junctions connect to each other. A guard placed at a junction watches every walkway that touches that junction. We need the fewest junctions where guards must stand so every walkway has at least one guard at one of its two ends.
Step 2: Key Formula or Approach.
This is a minimum vertex cover problem: pick the smallest set of junctions (vertices) so every walkway (edge) has at least one chosen junction at one of its ends. Since every junction here touches exactly 2 walkways, one guard can cover at most 2 walkways. With 5 walkways in total, at least \(\lceil 5/2 \rceil = 3\) guards are needed, because 2 guards can cover at most \(2 \times 2 = 4\) walkways, which is not enough for 5.
Step 3: Detailed Explanation.
Label the junctions: T (top), L and R (the two middle junctions), and P and Q (the two bottom junctions). The 5 walkways are T-L, T-R, L-P, R-Q, and P-Q.
Try 2 guards first: no matter which 2 junctions are picked, together they touch at most 4 walkways (since each junction touches only 2), so one walkway is always left unwatched. So 2 guards, option (A), can never be enough.
Now try 3 guards, placed at T, P, and Q. Junction T covers walkways T-L and T-R. Junction P covers walkways L-P and P-Q. Junction Q covers walkways R-Q and P-Q. Between T, P, and Q, all 5 walkways are watched, with P-Q watched twice. So 3 guards are enough.
Since 2 guards are proved impossible and 3 guards are shown to work, the minimum is exactly 3.
Step 4: Final Answer.
The minimum number of guards needed is 3, which is option (B). Options (C) and (D) use more guards than necessary, so they are not the minimum even though they would also work.
\[ \boxed{3} \]
