0
$\begingroup$

So the problem goes: we have a $n\cdot n$ board, where there is a number on each square, representing the number of rectangles of the board, which contain that square. What is the sum of all such numbers?

I'm really just a beginner at discrete mathemathics, and we didn't finish this problem at uni, and it's been bothering me since I'm unsure what to do here.

An idea was to put the board in a coordinate system and view each square as $(i,j)$ which are $\in$ $P_{a,b,c,d}$ (rectangles). And from there proceeding onto some strange summations, but that proved useless. An approach using matrices also didn't get too far.

I'm really lost here so any hints whatsoever would be really useful, I wish I had more ideas to offer!

Thank you in advance!

$\endgroup$
2
$\begingroup$

Imagine a formula for the number of rectangles containing the square at $(i, j)$. Such a rectangle goes horizontally from $a$ to $b$ for some $a,b$ where $a\le i \le b$, and goes vertically from $c$ to $d$ for some $c,d$ where $c\le j\le d$.

For a square at $(i,j)$, there are $i$ possibilities for $a$, $n-i+1$ possibilities for $b$, $j$ possibilities for $c$, and $n-j+1$ possibilities for $d$. Since the choices for $a,b,c,d$ are independent, there are $ij(n-i+1)(n-j+1)$ possible rectangles containing the square at $(i,j)$. So your final answer will be $$\sum_{i=1}^n\sum_{j=1}^n ij(n-i+1)(n-j+1)$$ Do you think you can evaluate this sum?

$\endgroup$
  • $\begingroup$ Yeah, I see it, thanks a lot!! $\endgroup$ – Collapse Oct 12 '17 at 22:00
3
$\begingroup$

Another approach is: the sum is equal to the sum over all possible rectangles of their areas. To see this: imagine that you start with a grid of zeros, and then one by one, you draw each rectangle and add 1 to each square within that rectangle. Then at the end, you get the grid you described; whereas at each step, the sum increases by the area of the rectangle.

Now, to further simplify things, this sum is also equal to the number of ways to choose a rectangle and then an individual square within this rectangle. This is equivalent to choosing a pair of left and right edge coordinates $x_1, x_2$ satisfying $0 \le x_1 < x_2 \le n$; a pair of bottom and top edge coordinates $y_1, y_2$ satisfying $0 \le y_1 < y_2 \le n$; and then the bottom left corner of the square $(x_0, y_0)$ satisfying $x_1 \le x_0 < x_2$ and $y_1 \le y_0 < y_2$. By replacing $x_0$ by $x_0 + 1$, $x_2$ by $x_2 + 1$, and similarly for $y$, we get a bijection with the set of 6-tuples $(x_1, x_2', x_0', y_1, y_2', y_0')$ with $0 \le x_1 < x_0' < x_2' \le n+1$ and $0 \le y_1 < y_0' < y_2' \le n+1$. It is now easy to see this is equal to $\binom{n+2}{3}^2$.

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