I'm trying to figure out the minimum number of rectangles required to cover an $n \times n$ grid, minus the diagonal. What this is means is the following: Suppose we have an $n \times n$ grid, with the diagonal missing. What is the minimum umber of rectangles I need that are contained within the grid such that the union of the rectangles covers the entire grid?
I think the answer should be $\log_2 n$. Attainment is easy, there are two $n^2/4$ squares (by which I mean two squares with area $n^2/4$), four $n^2/16$ squares, 8 $n^2/64$ squares, and so on. Summing this (and assuming $n = 2^m$) you get $$ \sum_{k=1}^{m = \log_2 n} 2^k \cdot n^2/4^k = \sum_{k=1}^m n^2 2^{-k} = n^2(1 - 1/n) = n^2 - n. $$ But I don't see a clean way to argue that this is the best you can do.
Suppose that each square in the grid has coordinates $i,j$ representing its row and column. Take a look at squares: (1,2), (2,3), (3,4), ..., ($n$-1, $n$) above the diagonal and (2,1), (3,2), ..., ($n$, $n-1$) under the diagonal. There is no rectangle covering any two squares picked from this set at the same time.
So you need at least $2(n-1)$ rectangles just to cover all squares from this set. Fortunately, you can cover the whole board with the same number of rectangles (a set of horizontal rectangles of height 1 will do the job).
So the minimum number of rectangles is really $2(n-1)$.