GATE EC 2022 Set 1 — Question 4

Let the grid be a $4 \times 4$ grid. The unshaded unit square represents a hole. We need to find the maximum number of squares without a "hole in the interior".Assume the hole is at position $(2,2)$ in a 1-indexed grid. There are $4 \times 4 = 16$ unit squares in total.
One square contains the hole.
Number of $1 \times 1$ squares without a hole = $16 - 1 = 15$. The number of possible $2 \times 2$ squares in a $4 \times 4$ grid is $(4-2+1) \times (4-2+1) = 3 \times 3 = 9$.
A $2 \times 2$ square contains the hole if its top-left corner is at $(1,1)$, $(1,2)$, $(2,1)$, or $(2,2)$. These are 4 squares.
Number of $2 \times 2$ squares without a hole = $9 - 4 = 5$. The number of possible $3 \times 3$ squares in a $4 \times 4$ grid is $(4-3+1) \times (4-3+1) = 2 \times 2 = 4$.
All these 4 squares (top-left corners at $(1,1)$, $(1,2)$, $(2,1)$, $(2,2)$) will contain the hole at $(2,2)$.
Number of $3 \times 3$ squares without a hole = $4 - 4 = 0$. There is only $1$ possible $4 \times 4$ square.
This square contains the hole.
Number of $4 \times 4$ squares without a hole = $1 - 1 = 0$.Total maximum number of squares without a "hole in the interior" = $15 + 5 + 0 + 0 = 20$.The final answer is $\boxed{\text{20}}$