, 2007

Let $(i, j)$ denote the square on the intersection of the $i$-th row and the $j$-th column.

First, let us show that $n = 28$ works. Remove the squares one by one. The initial grid can be divided into $1$ good rectangle. If $1$ square is removed from a good rectangle, we can divide the remaining part into $4$ or less good rectangles as shown in the figure below. By this method we can divide the final grid into $1 + 3 \times 9 = 28$ or less good rectangles.

Now we only have to show that $n$ with the property in this problem is more than or equal to $28$. We will show $28$ rectangles are needed when $(2, 2), (4, 4), \dots, (18, 18)$ are removed. Paint all squares which are next to the removed ones in red. We have $36$ red squares. Rectangles containing $(1, 2), (2, 1), (18, 19)$ or $(19, 18)$ cannot have another red square inside it. For a rectangle with other red squares, we can assume, by rotating and flipping, that it contains square $A$ in the picture below.

It cannot contain dotted squares because such rectangle contains some removed squares. The only red squares that are not dotted are $B$ and $C$. A rectangle with $A$ in its inside cannot contain $B$ and $C$ together, and if it contains $B$ or $C$ it also have $D$ in it.

So no rectangles have $3$ red squares and every rectangle with $2$ red squares contains some square of the form $(2k + 1, 2k + 1)(1 \le k \le 8)$. Therefore $n \ge (36 - 2 \times 8) + 8 = 28$.