You are given N square tiles of dimension 1×1. You have to arrange them in form of a grid such that total number of rectangle (of all possible dimensions) is maximum. Hollows within the grid are not allowed. The grid should be a complete rectangle. Only extra tiles after a complete rectangle can be placed on the side to form additonal rectangles.
Example: When N=8
27 Rectangles
_ _
|_|_|_
|_|_|_|
|_|_|_|
30 Rectangles
_ _ _ _
|_|_|_|_|
|_|_|_|_|
36 Rectangles
_ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|
Hence, 36 rectangles is desirable. Can anyone help me in formulating the formula for the same in terms of N?
I received this problem from a friend who in turn might have recieved it from assignment or a maths contest. My first thought of solving this problem is for each integer value of row calculate maximum possible columns and then put the remaining tiles along the smaller side(so that those tiles can form maximum combination with bigger side) . This way we might have to try out rows from 1 to $\sqrt N$ . Now I hear there can be better approach than this. Let me know if you can think of any.
Let us require that the grid be a full rectangle for simplicity. Then given $N$ we can factor it as $a \times b$ with $a\le b$ and make such a grid. We select two rows and two columns with replacement to get a rectangle. There are $\frac 12a(a+1)$ ways to select the rows and $\frac 12b(b+1)$ ways to select the columns for $\frac 14ab(a+1)(b+1)$. Assuming $N$ is a square, the limiting cases are $a=1,b=N$ and $a=b=\sqrt N$. In the first case we get $\frac 12N(N+1)$ rectangles. In the second we get $\frac 14N(\sqrt N+1)^2=\frac 14N^2+\frac 12N^{3/2}+\frac 14N$ rectangles. If $N=4$ the $2 \times 2$ has $9$ rectangles while the $1 \times 4$ has $10$. The $1 \times N$ grid dominates.
The way to make this rigorous is to show that decreasing $a$ always increases the number of rectangles, showing that $a=1$ is optimal.