Let $n$ be a positive integer.

a) A square of side $n$ is divided into $n^{2}$ unit squares by lines parallel to its sides. Determine the number of rectangles whose vertices are vertices of unit squares and that have sides parallel to the sides of the original square.

b) Three squares of side $n$ are arranged as shown in the figure below, and each of them is divided into $n^{2}$ unit squares by lines parallel to their sides. Determine the number of rectangles whose vertices are vertices of unit squares and that have sides parallel to the sides of the three original squares.

![](https://cdn.mathpix.com/cropped/2024_05_01_40ea5c1759d4b041c087g-33.jpg?height=180&width=174&top_left_y=1672&top_left_x=1044)
Solution

a) The vertices of the rectangles are uniquely determined by the intersections of two of the $n+1$ vertical and parallel lines with two of the $n+1$ horizontal lines parallel to the sides of the square that delimit the unit squares. We can choose the first vertical line in $n+1$ ways and the second in $n+1-1=n$ ways. Moreover, choosing a line $r$ and then a line $s$ is the same as choosing $s$ and then $r$. Thus, the total number of choices of pairs of vertical lines is $\frac{n \cdot(n+1)}{2}$. Similarly, the total number of choices of horizontal lines is $\frac{n(n+1)}{2}$. Therefore, the number of rectangles sought is

$$
\left(\frac{n \cdot(n+1)}{2}\right)^{2}
$$

b) Let's complete the given figure to obtain a square of side $2n$ subdivided into $(2n)^2$ unit squares. We already know that in such a configuration there are

$$
\left(\frac{2n(2n+1)}{2}\right)^2 = n^2 \cdot (2n+1)^2
$$

rectangles with vertices on the unit squares and sides parallel to the sides of the square. We want to remove from this count the rectangles that have at least one vertex in the new region added to the given figure. These unwanted rectangles can have one, two, or four vertices within the square of side $n$ added to the figure. Let's see the number of such rectangles in each case:

i) To count the rectangles with four vertices in the new square, it suffices to appeal again to part a) and obtain

$$
\left(\frac{n \cdot(n+1)}{2}\right)^{2}
$$

rectangles.

ii) To count the rectangles with two vertices in the new square, note that they will either be on a vertical or horizontal line. Suppose initially that the two vertices in the new region are on a vertical line. We can choose it in $n$ ways, corresponding exactly to the $n$ last vertical lines on the right. The other vertical line that contains the other vertices outside the new region can be chosen in $n$ ways, corresponding exactly to the $n$ first vertical lines on the left. Thus, we have $n \cdot n = n^2$ choices for the vertical lines. To choose the horizontal lines, since we are assuming that there are exactly two vertices in the new region, they must be chosen from the $n+1$ first horizontal lines at the top. Since the order of choosing them does not matter, we have $\frac{n \cdot (n+1)}{2}$ possible choices of vertical lines. The other possibility, where the two vertices are on a horizontal line, is analogous and it is only necessary to double the count we made previously to include them. Consequently, the total number of unwanted rectangles in this case is

$$
2 \cdot n \cdot n \cdot \frac{n \cdot (n+1)}{2} = n^3(n+1)
$$

iii) Finally, to count the rectangles with only one vertex in the new region, note that it is the intersection of one of the $n$ last vertical lines with one of the $n$ first horizontal lines. Therefore, we can choose these lines in $n \cdot n = n^2$ ways. To choose the other lines that will determine the other vertices of the rectangle, we must choose a vertical line from the $n$ first and a horizontal line from the $n$ last. Therefore, the total number of rectangles in this case is

$$
n \cdot n \cdot n^2 = n^4
$$

To complete the count, we just need to eliminate the unwanted rectangles that we have just calculated, and thus we obtain as the answer the number:

$$
n^2 \cdot (2n+1)^2 - n^4 - n^3(n+1) - \left(\frac{n(n+1)}{2}\right)^2
$$