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
Model the diagram as a graph: junctions are vertices, walkways are edges. The minimum number of guards is the minimum vertex cover of that graph. The diagram forms a 5 junction ring, and an odd ring of size n needs at least ceil(n/2) guards.
Step 1: Read the diagram as a graph. Each black dot is a junction (a vertex) and each line joining two dots is a walkway (an edge). Label the top dot T, the two shoulder dots L (left) and R (right), and the two bottom dots BL (bottom left) and BR (bottom right). The walkways shown are: T-L, T-R, L-BL, R-BR, and BL-BR.
Step 2: Notice that these five walkways form a single closed loop. Starting at T and following the lines: T to L, L to BL, BL to BR, BR to R, and R back to T. This visits all 5 junctions once and returns to the start, so the graph is a cycle with 5 vertices, usually written \[ C_5 \]
Step 3: Restate the guard requirement as a vertex cover problem. A guard placed at a junction can watch every walkway that touches that junction. We need the smallest set of junctions such that every walkway has at least one of its two end junctions guarded. This is exactly the minimum vertex cover of the graph.
Step 4: Work out the minimum vertex cover of a 5 cycle. Try 2 guards first: with only 2 junctions guarded, at most 2 times 2 = 4 walkways can be covered (each junction touches 2 walkways in this cycle), but there are 5 walkways in total, so at least one walkway would be left unguarded. Hence 2 guards are not enough. Now try 3 guards: place guards at L, BR, and T. Check each walkway: T-L is covered by T (and L). T-R is covered by T. L-BL is covered by L. R-BR is covered by BR. BL-BR is covered by BR. All five walkways are covered, so 3 guards are enough.
Step 5: Confirm 3 is the minimum. In general, for an odd cycle with \(n\) junctions, the minimum vertex cover has size \[ \left\lceil \frac{n}{2} \right\rceil \] junctions, because no set of fewer junctions can touch every edge of an odd loop without leaving a gap. For \(n=5\), this gives \[ \left\lceil \frac{5}{2} \right\rceil = 3 \]
Final Answer: The minimum number of guards needed is 3, which matches option (B). \[ \boxed{3} \]
Find dV/dt