GATE 2022 EE GA Q.10: solution and answer

GATE 2022 · EEGA Q.10 · 2 marks · MCQ

[Figure: a 4 x 4 square grid with P at its bottom-left corner]

An ant is at the bottom-left corner of a grid (point P) as shown above. It aims to move to the top-right corner of the grid. The ant moves only along the lines marked in the grid such that the current distance to the top-right corner strictly decreases.

Which one of the following is a part of a possible trajectory of the ant during the movement?

GATE 2022 EE GA question 10: Question figure: a 4 x 4 grid of equal squares (5 horizontal lines and 5 vertical lines, so 5 x 5 lattice points). — Figure from the GATE 2022 EE paper. It is part of the question.

(A)
Figure: from P, one unit segment goes right along the bottom (and ends) and one goes up. From the top of the upward segment the path goes right 1, up 1, right 1, then down 1, where it ends.
(B)
Figure: a stroke that starts one unit above P and comes down to P, then goes right 1, up 2, right 1, then down 1, where it ends.
(C)
Figure: a staircase from P going up 1, right 1, up 1, right 1.
(D)
Figure: a closed unit square with P at its bottom-left corner (right 1, up 1, left 1, down 1 back to P).

Answer and solution

ANSWER

The answer is (C). The staircase up, right, up, right starting from P uses only moves that bring the ant closer to the top-right corner, and it can be continued all the way to that corner. Options (A), (B) and (D) each need a downward or leftward move, or a return to P.

Official answer: CSource: Official answer key, GATE 2022 EE (IIT Kharagpur)

Put P at $(0, 0)$ . The grid has $4 \times 4$ squares, so the top-right corner is at $(4, 4)$ . The ant moves only along grid lines, so at every moment it is moving right, left, up or down, and it always stays inside the grid ( $0 \leq x \leq 4, 0 \leq y \leq 4$ ).
From a point $(x, y)$ the distance to the top-right corner is $d = (4 - x)^{2} + (4 - y)^{2}$ where $4 - x \geq 0$ and $4 - y \geq 0$ . Moving right makes $4 - x$ smaller and moving up makes $4 - y$ smaller, so either move makes $d$ smaller. Moving left or down makes one of these gaps larger, so $d$ grows. The same is true of the along-the-grid distance $(4 - x) + (4 - y)$ .
So every segment of a valid trajectory must go up or to the right. And because $d$ strictly decreases, the ant can never come back to a point it has already visited. In particular it never returns to P. So if part of a trajectory contains P, then P is the first point of that part, and only one segment of that part can touch P.
(A) Two segments meet at P, one going right and one going up. The ant starts at P and cannot come back to it, so it cannot use both of them. Also, if it follows the upward route from P (up, right, up, right), the drawing ends with the step $(2, 2) \to (2, 1)$ . That is a downward move, which increases the distance. Rejected.
(B) Again two segments meet at P: the one from $(0, 1)$ and the one going right. To use the segment $(0, 1) \to (0, 0)$ the ant would have to arrive at P moving downward, but it starts at P and never returns there. The route it can follow from P (right, up, up, right) also ends with the downward step $(2, 2) \to (2, 1)$ . Rejected.
(D) A closed square brings the ant back to P, which needs a left move and a down move. It would finish at the same distance it started from, which is not a strict decrease. Rejected.
(C) The moves are up, right, up, right: $(0, 0) \to (0, 1) \to (1, 1) \to (1, 2) \to (2, 2)$ . The distance to $(4, 4)$ falls at every step: $32 \to 25 \to 18 \to 13 \to 8$
This staircase can also be finished off to reach the corner. For example, $(2, 2) \to (3, 2) \to (4, 2) \to (4, 3) \to (4, 4)$ continues the distances as $5 \to 2 \to 1 \to 0$ , still strictly decreasing. So (C) is part of a possible trajectory. Answer: (C).

KEY IDEA

If the distance to the top-right corner must strictly decrease, every move has to be up or to the right. A left or down move takes the ant further away. So a valid trajectory is a staircase that goes only up and right. It never revisits a point, never comes back to P, and never has two branches leaving P.

WATCH OUT FOR

Picking (A) or (B) because most of their segments go up or right. Both end with a downward segment, and both have two segments meeting at P, which the ant could only use by coming back to its starting point. Another slip is choosing (D) because a square is made of grid lines, forgetting that going around it means moving left and down back to P.

From the GATE 2022 EE paper. Every question of this paper · Download the full paper · All 23 Spatial questions, with notes

GATE 2022 EE GA Q.10: solution and answer

Answer and solution

More Spatial questions