GATE 2022 EC GA Q.4: solution and answer

GATE 2022 · ECGA Q.4 · 1 mark · MCQ

The figure shows a grid formed by a collection of unit squares. The unshaded unit square in the grid represents a hole.

[Figure]

What is the maximum number of squares without a “hole in the interior” that can be formed within the $4 \times 4$ grid using the unit squares as building blocks?

GATE 2022 EC GA question 4: A 4 by 4 square grid made of 16 unit squares, with a black dot at each of its 25 grid-line intersections (5 by 5 lattice… — Figure from the GATE 2022 EC paper. It is part of the question.

(A)
15
(B)
20
(C)
21
(D)
26

Answer and solution

ANSWER

(B) 20. That is 15 unit squares plus 5 two-by-two squares that avoid the hole. Every 3 × 3 square and the full 4 × 4 grid contain the hole.

Official answer: BSource: Official answer key, GATE 2022 EC (IIT Kharagpur)

Number the rows 1 to 4 from the top and the columns 1 to 4 from the left, so the hole is cell $(2, 2)$ . A square built from unit squares as building blocks cannot include the hole anywhere, because the hole is a missing block. So we count only the squares that do not contain cell $(2, 2)$ .
A $4 \times 4$ grid has $(4 - k + 1)^{2}$ squares of side $k$ : that is $16, 9, 4, 1$ for $k = 1, 2, 3, 4$ , or 30 in all if the hole is ignored.
$1 \times 1$ : every unit square except the hole, so $16 - 1 = 15$ .
$2 \times 2$ : a square whose top-left cell is $(r, c)$ , with $r, c \in {1, 2, 3}$ , covers rows $r, r + 1$ and columns $c, c + 1$ . It contains $(2, 2)$ exactly when $r \in {1, 2}$ and $c \in {1, 2}$ , which gives $2 \times 2 = 4$ squares. So $9 - 4 = 5$ squares are free of the hole.
$3 \times 3$ : the top-left cell can only be $(1, 1), (1, 2), (2, 1)$ or $(2, 2)$ . Each of these squares covers rows 2 and 3 and columns 2 and 3, so all 4 contain the hole. That leaves 0.
$4 \times 4$ : the only such square is the whole grid, which contains the hole, so 0.
Total: $15 + 5 + 0 + 0 = 20$ The answer is (B).

KEY IDEA

For each size, count the squares by where their top-left cell sits, then subtract the ones that cover the hole. A square of side $k$ with top-left cell $(r, c)$ covers the hole $(2, 2)$ exactly when $r \leq 2 \leq r + k - 1$ and $c \leq 2 \leq c + k - 1$ . A hole near a corner leaves no room for 3 × 3 squares, because every 3 × 3 square in a 4 × 4 grid covers the two middle rows and the two middle columns.

WATCH OUT FOR

Counting the hole itself as a $1 \times 1$ square gives $16 + 5 = 21$ , which is option (C). Another mistake is to allow bigger squares that have the hole on their edge rather than at their centre, or to subtract only the $2 \times 2$ squares that contain the hole ( $30 - 4 = 26$ , option (D)). Stopping after the unit squares gives 15, option (A). Because the hole is a missing building block, no square that contains it can be formed at any size.

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

GATE 2022 EC GA Q.4: solution and answer

Answer and solution

More Spatial questions