The figure shows a grid formed by a collection of unit squares. The unshaded unit square in the grid represents a hole. What is the maximum number of squares without a 'hole in the interior' that can be formed within the 4 x 4 grid using the unit squares as building blocks? A. 15 B. 20 C. 21 D. 26
GATE 2022 · General Aptitude · Counting Figure · medium
Answer: Maximum number of squares without a hole in the interior = 20 (Option B).
- Count all squares in a 4x4 grid: For n=4: 1x1: (4)^2=16; 2x2: (3)^2=9; 3x3: (2)^2=4; 4x4: (1)^2=1. Total = 16+9+4+1 = 30.
- Identify hole position and count squares containing it: From the figure the hole is at row 3, col 3 (1-indexed). A k x k square with top-left at (r,c) contains cell (3,3) when r <= 3 <= r+k-1 and c <= 3 <= c+k-1, i.e. r in [4-k, 3] and c in [4-k, 3]. Number of such squares = min(3, k) * min(3, k) = k^2 for k=1,2,3 and 1 for k=4. Counting: 1x1: 1 square (just the hole cell itself); 2x2: 4 squares; 3x3: 9 squares; 4x4: 1 square. Total squares containing the hole = 1+4+9+1 = ... but we check: for k=1, exactly 1 square contains (3,3). For k=2: top-left can be (2,2),(2,3),(3,2),(3,3) = 4 squares. For k=3: top-left can be (1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) = but capped to valid positions; top-left r in [1,2], c in [1,2] gives 4 squares. Wait - for k=3 in a 4x4 grid the valid top-left positions are rows 1-2 and cols 1-2. The hole at (3,3) is contained if r<=3<=r+2 (r in {1,2,3} but capped to {1,2}) and c<=3<=c+2 (c in {1,2}). So 2*2=4 squares contain the hole. For k=4: only 1 square (the entire grid). Total = 1+4+4+1 = 10.
- Compute valid squares: valid = 30 - 10 = 20.