# Minimum number of rectangles to cover diagonal-free grid

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.

• log base 2 of n ?? I tried it for n=8 and I get 14 (7 on each side of the diagonal). But log base 2 of n for n=8 gives 3 ??? Jan 27 '19 at 4:00
• "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" This seems to only hold for even values of n.. in all the cases I've tested so far it seems that 2*(n-1) is the best solution. Jan 27 '19 at 4:12
• Can those rectangles overlap
– Aqua
Jan 27 '19 at 7:39

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