Problem Post 2-5: How many Shapes, Part 2: Rectangles in Rectangles

		Problem Posts
		Part 2 of 4 of How Many Shapes?

[Level 2-3]

So in my previous Miscellaneous post, we solved a fairly simple Internet puzzle, counting the number of squares in a square grid. But now, we ask ourselves if we can do more:

CAN WE DO BETTER?

• What if the original grid were a rectangle, instead of a square? Or an irregular figure?
• What if we were counting rectangles instead of squares?
• What if some of the grid 'wires' are missing?
• What if we're working on a triangular grid, counting triangles? Does our logic still apply?

1 Rectangles in Rectangles

So now let's try to generalize our square counting result to counting rectangles in rectangular grids.

PROBLEM 1
We have an $10$ by $20$ rectangular grid.

• Given a certain size of rectangle (say, $4\times 5$), how many such rectangles can be found in that grid, oriented so that the side with length $4$ lines up with the side with length $10$ on the grid? Find a general way to do this for any size grid, and any size rectangle.
• How many rectangles of all sizes are in the grid?

1.1. Rectangles of a certain size

It's clear that the first sub-problem can be solved by replicating our original strategy with the square-counting problem. We look at where we can place the upper left squarelet (or upper left corner, whichever you prefer) of the rectangle.

The upper left squarelet can be anywhere in the first $10-4+1=7$ columns of the grid, and the first $20-5+1=16$ rows. Note that if you place it anywhere else, the resulting $4\times 5$ rectangle would lie outside the grid. Also, every valid choice for where to place the upper left squarelet uniquely determines one rectangle.

So we're done:

SOLUTION 1a  $$(10-4+1)\times(20-5+1)=\boxed{112}$$

Next,  it's time to generalize! What if we had an $m\times n$ grid, and we wanted to look for $i\times j$ sized rectangles? It's easy to think the answer is $$(m-i+1)\times(n-j+1)$$ But what if $m<i$ or $n<j$? For example, if we have $m=n=10$ and $i=j=20$, then $(m-i+1)\times(n-j+1)=81$ which is certainly wrong because there are zero rectangles of size $20\times 20$ in a $10\times 10$ grid!

We need a way to "zero out" something when it goes wrong. So we introduce some convenient notation:

DEFINITION

Let $$\left(x\right)^{+}=\begin{cases} x & \text{if }x\text{ is positive}\\ 0 & \text{otherwise} \end{cases}$$ So for example, $(3)^+ = 3$, $(-4)^+=0$, and the graph $f\left(x\right)=(x)^+$ is a flat line on $\left(-\infty,0\right)$, and linear with slope 1 on $\left(0,\infty\right)$.

Now, if we write   $$(m-i+1)^+\times(n-j+1)^+$$ the formula is correct for any conceivable $m,n,i,j\in \mathbb{N}_{>0}$. Plugging in  $m=n=10$ and $i=j=20$, we get 0, which is sensible.

1.2. Rectangles of any size

Now, the next order of the day is to figure out how many rectangles there are all-in-all. But that's easy, right? Find out how many $1\times 1$ rectangles there are, then $1\times 2$, then $2\times 1$, and so on, so we have $$\sum_{i=1}^{m}\sum_{j=1}^{n}\left(m-i+1\right)^{+}\left(n-i+1\right)^{+}$$ Good luck doing that in fifteen seconds.

We clearly need a better way to do this. Each rectangle can be identified uniquely by its the left edge $x_1$, right edge $x_2$, bottom edge $y_1$, and top edge $y_2$, as in the GIF below:

So we have reduced the problem accordingly:

PROBLEM 1b, modified
How many quadruples of integers $(x_1,x_2,y_1,y_2)$ are there for which $0\le x_1 <x_2 \le 20$, and $0 \le y_1<y_2 \le 10$?

It may look uglier, but now the solution is clear: any choice of two things from $0$ to $20$ is good for $x_1$ and $x_2$; ditto for $y_1$ and $y_2$ but they can go up to $20$. Order is not important because automatically we have $x_1<x_2$ and $y_1<y_2$. So we have

SOLUTION 1b  $$\binom{10+1}{2}\binom{20+1}{2}=\boxed{11550}$$

This generalizes easily to  $$\binom{m+1}{2}\binom{n+1}{2}=\frac{mn\left(m+1\right)\left(n+1\right)}{4}$$

1.3 Complications: What if gridlines are missing?

Let's say your grid is huge but it's not completely filled in:

How do we do this? One way around it is to count as usual, then subtract out the rectangles that cannot exist because of the gap.

But what about this situation?

Here the gaps are numerous and close to each other; if we performed a negative analysis, we would subtract out some rectangles twice, or more times (Why? Because they use more than one of the missing wires.) Since the grid is relatively small, it is expedient to simply count the rectangles one by one.

Summary

TOOLKIT: Counting Rectangles and Squares

• In an $m\times n$ rectangular grid, there are $\left(m-i+1\right)^{+}\left(n-j+1\right)^{+}$ rectangles of size $i\times j$ (oriented so that $i$ corresponds with $m$, and $j$ with $n$).
• In particular, there are $\left(m-i+1\right)^{+}\left(n-i+1\right)^{+}$ squares of size $i\times i$.
• The total number of rectangles of any size is $$\binom{m+1}{2}\binom{n+1}{2}=\frac{mn\left(m+1\right)\left(n+1\right)}{4}$$
• Supposing $n\le m$, the total number of squares of any size is $$\sum_{i=1}^{n}\left(m-i+1\right)\left(n-i+1\right)=mn^{2}-\frac{n\left(n-1\right)\left(3m+n+1\right)}{6}$$
• In particular, if $n=m$, the total number of squares is $$n^{3}-\frac{n\left(n-1\right)\left(4n+1\right)}{6}=\frac{n\left(n+1\right)\left(2n+1\right)}{6}$$
• If there are missing gridlines, choose between counting one by one, or subtracting affected rectangles from the original count.

This post has become far too long, so we'll do triangle counting in another one.