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 ________. (The diagram shows five junctions joined in a closed loop shaped like a pentagon: a top junction connects down to an upper-left junction and an upper-right junction, the upper-left junction connects down to a lower-left junction, the upper-right junction connects down to a lower-right junction, and the lower-left and lower-right junctions connect to each other. This gives 5 junctions and 5 walkways in total.)
Show Hint
Model the junctions and walkways as a 5-sided loop (pentagon). This needs a minimum vertex cover, which for a 5-cycle is 3.
Step 1: Turn the picture into a graph.
Label the five junctions in the diagram: the top point as A, the upper-left corner as UL, the upper-right corner as UR, the lower-left corner as LL, and the lower-right corner as LR.
The walkways (lines) join A to UL, A to UR, UL to LL, UR to LR, and LL to LR. This gives 5 walkways in total, connecting the 5 junctions in one closed loop shaped like a pentagon.
Step 2: Understand what placing a guard does.
A guard placed at a junction can watch every walkway that touches that junction, but not walkways that do not touch it.
We need to pick the smallest possible set of junctions so that every one of the 5 walkways has at least one of its two ends covered by a guard.
Step 3: Check whether 2 guards are enough.
Each junction touches exactly 2 walkways, so 2 guards can cover at most 4 walkway-ends between them if they do not share a walkway, and even fewer distinct walkways if they do.
Try guards at A and LL: this covers A-UL, A-UR, UL-LL, and LL-LR, but leaves UR-LR unwatched.
Try guards at UL and LR: this covers A-UL, UL-LL, UR-LR, and LL-LR, but leaves A-UR unwatched.
Every choice of 2 junctions leaves at least one walkway with neither end covered, because 5 walkways cannot all be covered by only 4 walkway-ends. So 2 guards are never enough.
Step 4: Check that 3 guards are enough.
Place guards at A, LL, and LR.
A covers A-UL and A-UR.
LL covers UL-LL and LL-LR.
LR covers LL-LR and UR-LR.
Together, all 5 walkways (A-UL, A-UR, UL-LL, UR-LR, LL-LR) have at least one guarded end, so all walkways are watched.
Final Answer:
2 guards are never enough, and 3 guards are enough when placed correctly, so the minimum number of guards needed is 3.
\[ \boxed{3} \]
