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

Label the five junctions as T (top), L and R (the two middle points), and P and Q (the two bottom points). The five walkways connecting them are T-L, T-R, L-P, R-Q, and P-Q, forming one closed loop of 5 junctions and 5 walkways. Every junction touches exactly 2 walkways, since it is a simple closed loop. A guard at a junction only watches the walkways meeting there, so we need the smallest set of junctions whose walkways together cover all 5 lines. Check each option against a lower bound: since one guard can watch at most 2 walkways, $g$ guards can watch at most $2g$ walkways, and we need $2g \geq 5$, so $g \geq 2.5$, meaning $g$ must be at least 3.

2 guards: At most $2 \times 2 = 4$ walkways can be watched, but there are 5 walkways to cover, so at least one is always missed. This count fails.
3 guards: Placing guards at T, P, and Q covers T-L, T-R (from T), L-P, P-Q (from P), and R-Q, P-Q (from Q). All 5 walkways are covered. This count works and matches the lower bound of 3, so it is the minimum.
4 guards: This also covers every walkway, since it is more than needed, but it is not the minimum because 3 already succeeds.
5 guards: One guard on every junction certainly covers all walkways, but again this is far more than the minimum of 3.

The smallest number of guards that both satisfies the lower bound calculation and is confirmed to cover every walkway by direct placement is 3.

Let's summarize:

Each junction touches exactly 2 walkways, so $g$ guards can cover at most $2g$ walkways.
With 5 walkways, $2g \geq 5$ forces $g \geq 3$.
Placing guards at the top junction and the two bottom junctions (T, P, Q) covers all 5 walkways with exactly 3 guards.

So the minimum number of guards required is 3, option (B).

Answer 2

Label the five junctions as T (top), L and R (the two middle points), and P and Q (the two bottom points). The five walkways connecting them are T-L, T-R, L-P, R-Q, and P-Q, forming one closed loop of 5 junctions and 5 walkways. Every junction touches exactly 2 walkways, since it is a simple closed loop. A guard at a junction only watches the walkways meeting there, so we need the smallest set of junctions whose walkways together cover all 5 lines. Check each option against a lower bound: since one guard can watch at most 2 walkways, $g$ guards can watch at most $2g$ walkways, and we need $2g \geq 5$, so $g \geq 2.5$, meaning $g$ must be at least 3.

2 guards: At most $2 \times 2 = 4$ walkways can be watched, but there are 5 walkways to cover, so at least one is always missed. This count fails.
3 guards: Placing guards at T, P, and Q covers T-L, T-R (from T), L-P, P-Q (from P), and R-Q, P-Q (from Q). All 5 walkways are covered. This count works and matches the lower bound of 3, so it is the minimum.
4 guards: This also covers every walkway, since it is more than needed, but it is not the minimum because 3 already succeeds.
5 guards: One guard on every junction certainly covers all walkways, but again this is far more than the minimum of 3.

The smallest number of guards that both satisfies the lower bound calculation and is confirmed to cover every walkway by direct placement is 3.

Let's summarize:

Each junction touches exactly 2 walkways, so $g$ guards can cover at most $2g$ walkways.
With 5 walkways, $2g \geq 5$ forces $g \geq 3$.
Placing guards at the top junction and the two bottom junctions (T, P, Q) covers all 5 walkways with exactly 3 guards.

So the minimum number of guards required is 3, option (B).

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 GG exam