Japan 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$.