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

Question

In the 2020 summer Olympics' Javelin throw finals, Neeraj Chopra exhibited a spectacular performance to win the gold medal. The silver medal was won by Jakub Vadlejch and the bronze medal was won by Vitezlav Vesely. There were six rounds of throws with each athlete having one throw per round. The best of all the throws of each athlete is considered for the medal. Following were the observations about the throws:
(i) The first and second rounds were dominated by Neeraj Chopra with a gold medal performance in his second throw, while the other two athletes did not have any medal winning throws in these rounds.
(ii) The throws in the last round by both Jakub Vadlejch and Vitezlav Vesely were fouls and were not considered for scoring.
(iii) After four rounds, Vitezlav Vesely was in the second position and could not improve upon his best throw in the succeeding rounds.
(iv) In the fourth round, the throw by Jakub Vadlejch was the best in that round.
In which round did Vitezlav Vesely have his best throw?

Answer 1

Instead of quoting a formula for cycles, we can just try placing fewer and fewer guards and see what breaks. The diagram has 5 junctions joined in a ring: going around, top, left shoulder, bottom left, bottom right, right shoulder, and back to top, with 5 walkways total.

Trying 1 guard: a single junction only touches 2 of the 5 walkways, so 3 walkways would have no guard nearby. Not enough.
Trying 2 guards: two junctions touch at most 4 walkway ends between them (2 walkways each), but the ring has 5 walkways, and however the 2 guards are placed, at least one walkway ends up with neither of its junctions guarded. Not enough.
Trying 3 guards: place guards at the top junction, the left shoulder junction, and the bottom right junction. Walking through the 5 walkways one by one: top-left shoulder has both ends guarded, top-right shoulder has the top guarded, left shoulder-bottom left has the left shoulder guarded, bottom left-bottom right has the bottom right guarded, and bottom right-right shoulder has the bottom right guarded. Every single walkway has at least one guarded end.
Could 3 be beaten: since 2 guards were shown to always miss a walkway, 3 is the smallest number that works.

So the minimum number of guards is 3, confirmed by direct trial rather than a formula, which matches option (B).

Let's summarize:

The walkway diagram is a closed ring of 5 junctions and 5 walkways.
With only 1 or 2 guards, some walkway is always left unwatched.
Placing guards at 3 well chosen junctions, alternating around the ring, covers every walkway.

The correct answer is 3 guards.

Answer 2

Instead of quoting a formula for cycles, we can just try placing fewer and fewer guards and see what breaks. The diagram has 5 junctions joined in a ring: going around, top, left shoulder, bottom left, bottom right, right shoulder, and back to top, with 5 walkways total.

Trying 1 guard: a single junction only touches 2 of the 5 walkways, so 3 walkways would have no guard nearby. Not enough.
Trying 2 guards: two junctions touch at most 4 walkway ends between them (2 walkways each), but the ring has 5 walkways, and however the 2 guards are placed, at least one walkway ends up with neither of its junctions guarded. Not enough.
Trying 3 guards: place guards at the top junction, the left shoulder junction, and the bottom right junction. Walking through the 5 walkways one by one: top-left shoulder has both ends guarded, top-right shoulder has the top guarded, left shoulder-bottom left has the left shoulder guarded, bottom left-bottom right has the bottom right guarded, and bottom right-right shoulder has the bottom right guarded. Every single walkway has at least one guarded end.
Could 3 be beaten: since 2 guards were shown to always miss a walkway, 3 is the smallest number that works.

So the minimum number of guards is 3, confirmed by direct trial rather than a formula, which matches option (B).

Let's summarize:

The walkway diagram is a closed ring of 5 junctions and 5 walkways.
With only 1 or 2 guards, some walkway is always left unwatched.
Placing guards at 3 well chosen junctions, alternating around the ring, covers every walkway.

The correct answer is 3 guards.

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

The Correct Option is B

Solution and Explanation

Top Questions on Analytical Reasoning

Questions Asked in GATE IN exam