2
$\begingroup$

Let's say we have two integers $x$ and $y$ that describe one rectangle, if this rectangle is splitten in exactly $x\cdot y$ squares, each of size $1\cdot 1$, count the sum of areas of all rectangles that can be formed from those squares.

For example if $x = 2, y = 2$, we have $4$ rectangles of size $(1,1)$, $2$ rectangles of size $(1, 2)$, $2$ rectangles of size $(2, 1)$ and $1$ rectangle of size $(4,4)$. So the total answer is $4\cdot 1+ 2\cdot2 + 2\cdot2+1\cdot4 = 16$

Is there easy way to solve this for different $x$ and $y$?

$\endgroup$
3
$\begingroup$

I assume, in your example, you mean there is one rectangle of size $(2, 2)$, because there are none $(4, 4)$.

In general, we have $(x - a + 1) \times (y - b + 1)$ rectangles of size $(a, b)$: we need to choose how many empty columns we leave before the rectangle $(0, 1, 2, \dots \text{ or } x-a)$, and how many rows we leave above it $(0, 1, 2, \dots \text{ or } y-b)$

So, in total, we have this area $$ \sum_{a=1}^x \sum_{b=1}^y (x - a + 1) \times (y - b + 1) \times ab = \\ \sum_{a=1}^x \Big( a (x - a + 1) \sum_{b=1}^y b (y - b + 1)\Big) = \\ \big(\sum_{a=1}^x a (x - a + 1)\big) \big( \sum_{b=1}^y b (y - b + 1)\big) $$

We can simplify this further by examining the sequence $A_n = \sum_{a=1}^n a (n - a + 1)$.

If we examine the first few elements of this sequence $(1, 4, 10, 20, 35, 56)$, we can notice that the sequence of differences $(1, 3, 6, 10, 15, 21)$ is exactly the sequence of triangular numbers. If that holds true in general, $A_n$ is the sum of the first $n$ triangular numbers, i.e. $A_n = \frac{n(n+1)(n+2)}{6}$ as seen here.

Here's a proof that this indeed holds in general: $$ \begin{align} A_n - A_{n-1} = 1 \times n &+ 2 \times (n-1) + 3 \times (n-2) + \dots + n \times 1 \\ &- 1 \times (n-1) - 2 \times (n-2) - 3 \times (n-3) - \dots = (n-1) \times 1 = \\ &= n + (2 - 1) \times (n - 1) + (3 - 2) \times (n - 2) + \dots + (n - 2 - n + 1) \times 1 \\ &=\sum_{i=1}^n i = \frac{n(n+1)}{2}, \end{align} $$ which is indeed the $n^{\text{th}}$ triangle number.

Thus, the answer to the original question is $$\frac{x(x+1)(x+2)}{6} \times \frac{y(y+1)(y+2)}{6}$$ and, in the case $x=y=2$ this is indeed 4.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

It is useful to move from simpler cases to more complex ones!

Consider $1\times y$ rectangle. The sum of areas of all rectangles is: $$\begin{align}A_{1\times y}&=1\times y+2\times (y-1)+3\times (y-3)+\cdots +y\times 1=\\ &=\sum_{i=1}^yi\cdot (y-i+1)=\\ &=(y+1)\sum_{i=1}^y i-\sum_{i=1}^yi^2=\\ &=(y+1)\cdot \frac{y(y+1)}{2}-\frac{y(y+1)(2y+1)}{6}=\\ &=\frac{y(y+1)[3y+3-2y-1]}{6}=\\ &=\frac{y(y+1)(y+2)}{6}.\end{align}$$

Consider $2\times y$ rectangle. The sum of areas of all rectangles is: $$\begin{align}A_{2\times y}&=\color{red}{2}\times [1\times y+2\times (y-1)+3\times (y-3)+\cdots +y\times 1]+\\ &+\color{red}{1}\times [2\times y+4\times (y-1)+6\times (y-3)+\cdots +2y\times 1]=\\ &=\color{red}{2}\times [A_{1\times y}]+\color{red}{1}\times 2\times [A_{1\times y}]\\ &=(\color{red}2+\color{red}1\times 2)\times [A_{1\times y}]\\ &=4\cdot \frac{y(y+1)(y+2)}{6}.\end{align}$$

Consider $3\times y$ rectangle. The sum of areas of all rectangles is: $$\begin{align}A_{3\times y}&=\color{red}{3}\times [1\times y+2\times (y-1)+3\times (y-3)+\cdots +y\times 1]+\\ &+\color{red}{2}\times [2\times y+4\times (y-1)+6\times (y-3)+\cdots +2y\times 1]+\\ &+\color{red}{1}\times [3\times y+6\times (y-1)+9\times (y-3)+\cdots +3y\times 1]=\\ &=(\color{red}{3}+\color{red}2\times 2+\color{red}1\times 3)\times [A_{1\times y}]=\\ &=10\cdot \frac{y(y+1)(y+2)}{6}.\end{align}$$

And now consider $x\times y$ rectangle. The sum of areas of all rectangles is: $$\begin{align}A_{x\times y}&=\ \ \ \ \ \ \ \ \ \ \color{red}{x}\times [1\times y+2\times (y-1)+3\times (y-3)+\cdots +y\times 1]+\\ &+\color{red}{(x-1)}\times [2\times y+4\times (y-1)+6\times (y-3)+\cdots +2y\times 1]+\\ &+\color{red}{(x-2)}\times [3\times y+6\times (y-1)+9\times (y-3)+\cdots +3y\times 1]=\\ & \ \ \vdots\\ &+\ \ \ \ \ \ \ \ \ \ \ \color{red}{1}\times [x\times y+2x\times (y-1)+3x\times (y-3)+\cdots +xy\times 1]=\\ &=(\color{red}{x}+\color{red}{(x-1)}\times 2+\color{red}{(x-2)}\times 3+\cdots +\color{red}1\times x)\times [A_{1\times y}]=\\ &=[A_{x\times 1}]\cdot [A_{1\times y}]=\\ &=\frac{x(x+1)(x+2)}{6}\cdot \frac{y(y+1)(y+2)}{6},\end{align}$$ which complies with the brilliant answer given by Todor Markov (+1).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.