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.)

Question

Pointing to a photograph, a man says, "I have no brothers or sisters, but the father of the person in the photograph is my father’s son." Who is the person in the photograph?

Answer 1

The diagram is a closed loop of 5 junctions and 5 walkways, shaped like a pentagon: a top junction connects to two upper corners, each upper corner connects down to a lower corner, and the two lower corners connect to each other. This kind of closed loop with an odd number of junctions has a known minimum guard count, which can be worked out directly by testing each answer choice.

2 guards: With only 2 junctions chosen, at most 4 walkway-ends can be covered (2 walkways touch each junction), but there are 5 walkways in the loop. Since $2 \times 2 = 4$, which is less than 5, at least one walkway is always left with no guard at either end. So 2 guards can never watch every walkway.
3 guards: Choosing the top junction and the two lower corners covers every walkway: the top junction watches the two walkways running down from it, and each lower corner watches the walkway coming down to it plus the walkway joining the two lower corners. All 5 walkways end up watched, using only 3 guards.
4 guards: This works too (any 4 out of 5 junctions will cover all walkways, since only one junction is left unguarded), but it uses one more guard than necessary, so it is not the minimum.
5 guards: Placing a guard at every junction obviously watches every walkway, but this is far more than needed, so it is not the minimum either.

Since 2 guards are proven impossible and 3 guards are shown to work with an explicit placement, the smallest possible number of guards is 3.

Let's summarize:

With 5 walkways and each junction touching only 2 of them, 2 guards can cover at most 4 walkway-ends, so 2 is not enough.
Placing guards at the top junction and both lower corners covers all 5 walkways at once.
4 or 5 guards would also work but use more guards than the minimum required.

So the minimum number of guards needed to watch all the walkways is 3, which is option (B).

Answer 2

The diagram is a closed loop of 5 junctions and 5 walkways, shaped like a pentagon: a top junction connects to two upper corners, each upper corner connects down to a lower corner, and the two lower corners connect to each other. This kind of closed loop with an odd number of junctions has a known minimum guard count, which can be worked out directly by testing each answer choice.

2 guards: With only 2 junctions chosen, at most 4 walkway-ends can be covered (2 walkways touch each junction), but there are 5 walkways in the loop. Since $2 \times 2 = 4$, which is less than 5, at least one walkway is always left with no guard at either end. So 2 guards can never watch every walkway.
3 guards: Choosing the top junction and the two lower corners covers every walkway: the top junction watches the two walkways running down from it, and each lower corner watches the walkway coming down to it plus the walkway joining the two lower corners. All 5 walkways end up watched, using only 3 guards.
4 guards: This works too (any 4 out of 5 junctions will cover all walkways, since only one junction is left unguarded), but it uses one more guard than necessary, so it is not the minimum.
5 guards: Placing a guard at every junction obviously watches every walkway, but this is far more than needed, so it is not the minimum either.

Since 2 guards are proven impossible and 3 guards are shown to work with an explicit placement, the smallest possible number of guards is 3.

Let's summarize:

With 5 walkways and each junction touching only 2 of them, 2 guards can cover at most 4 walkway-ends, so 2 is not enough.
Placing guards at the top junction and both lower corners covers all 5 walkways at once.
4 or 5 guards would also work but use more guards than the minimum required.

So the minimum number of guards needed to watch all the walkways is 3, which is option (B).

Show Hint

The Correct Option is B

Solution and Explanation

Top Questions on Logical Reasoning

Questions Asked in GATE MA exam