Counting Rectangles

By counting carefully it can be seen that a rectangular grid measuring $3$ by $2$ contains eighteen rectangles:

Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

To solve this question, we should break down how the rectangles in a rectangle grid are formed. Consider a rectangular grid of size m by n, every rectangle is defined by selecting two different horizontal borders and two different vertical borders of the grid.

There are m+1 horizontal borders and n+1 vertical borders. So, the number of rectangles in an m by n grid would be:

Number of rectangles = [(m+1) choose 2] * [(n+1) choose 2]

where “choose” is a combination (the number of ways of picking unordered combinations of things), which is calculated as:

n choose k = n! / [k!(n-k)!]

where n! denotes the factorial of number n.

So by substituting “choose” we get:

Number of rectangles = [m*(m+1)/2] * [n*(n+1)/2]

We need to look for the rectangular grid (m by n) with the number of rectangles as close as possible to 2 million.

One way to solve this task is by using brute-force computation:

Iterate over possible values for m and n, starting from 1 upwards, calculate the number of rectangles and compare it with 2 million. Terminate the loops when the number of rectangles exceeds 2 million for given m and n.

You will find that the dimensions that give the total closest to 2 million rectangles are m=77 and n=36. The total amount of rectangles you can build with these dimensions is 1999998. In other words, the area of the grid with the nearest solution to two million rectangles will be m*n = 77*36 = 2772.

More Answers: