2
$\begingroup$

How many squares exist in an $n \times n$ grid? There are obviously $n^2$ small squares, and $4$ squares of size $(n-1) \times (n-1)$.

How can I go about counting the number of squares of each size?

$\endgroup$
  • $\begingroup$ Can you count the number of $m \times m$ squares, for any $1 \le m \le n$? $\endgroup$ – arkeet Sep 26 '16 at 16:07
  • $\begingroup$ $\Sigma i^2 = \dfrac{n(n+1)(2n+2)}{6}$ $\endgroup$ – Shailesh Sep 26 '16 at 16:22
  • $\begingroup$ Continue your logic. On one side of the grid there are n segments of length 1. So n^2 1x1 squares. There are n-1 segments of length 2. So (n-1)(n-1) 2x2 squares. There are n - i+i segments of length i. so (n-i+i)(n-i+1) ixi squares. So $\sum_{i=0}^{n-1}(n-i)^2 = \sum_{k=1}^n k^2$ squares total. $\endgroup$ – fleablood Sep 26 '16 at 17:25
4
$\begingroup$

Another way to view this: for each size, there is one square that you move inside the larger one.

How much can it move? A square of size $k\times k$ inside a square of size $n\times n$ has $n-k+1$ possible positions in each direction (up-down and left-right): consider the position of the top left corner for instance. Hence there are $(n-k+1)^2$ such squares.

Can you finish from here?

$\endgroup$
  • $\begingroup$ Now I sum over k. This collapses to a sum of squared integers not greater than n. Thanks! $\endgroup$ – Demetri Pananos Sep 26 '16 at 16:32
0
$\begingroup$

NOTE:

For $n\times n$ grid the answer is $n^2+(n-1)^2+(n-2)^2+.....+1^2$

So, the answer is $$ \frac{n(n+1)(2n+1)}{6} $$

$\endgroup$
0
$\begingroup$

Another way of counting:

For each $(i, j, k)$ with $1 \le i, j \le n$ and $0 \le k \le \min(n-i, n-j)$ there is a square with upper left corner at $(i, j)$ and lower right corner at $(i+k, j+k)$.

Therefore the total is

$\begin{array}\\ s(n) &=\sum_{i=1}^n \sum_{j=1}^n (1+\min(n-i, n-j))\\ &=\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} (1+\min(i, j))\\ &=n^2+\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \min(i, j)\\ &=n^2+\sum_{i=0}^{n-1} (\sum_{j=0}^{i-1} \min(i, j)+\sum_{j=i} \min(i, j)+\sum_{j=i+1}^{n-1} \min(i, j))\\ &=n^2+\sum_{i=0}^{n-1} (\sum_{j=0}^{i-1} j+i+\sum_{j=i+1}^{n-1} i)\\ &=n^2+\sum_{i=0}^{n-1} (\frac12i(i-1)+i+i(n-1-(i+1)+1))\\ &=n^2+\sum_{i=0}^{n-1} (\binom{i}{2}+i+i(n-i-1))\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\sum_{i=0}^{n-1} (ni-i(i+1))\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\frac12 n^2(n-1)-\sum_{i=1}^{n} i(i-1)\\ &=n^2+\binom{n}{3}+\frac12 n(n-1)+\frac12 n^2(n-1)-2\binom{n+1}{3}\\ &=\frac13(n+1)n(n-1)\\ \end{array} $

$\endgroup$
0
$\begingroup$

Let the vertices of the $n \times n$ grid by $\{(x,y)| 0\le x \le n; 0 \le y \le n\}$.

(Is that what an $n \times n$ grid is? A $1 \times 1$ has $4$ vertices and an $n \times n$ grid has $(n+1)^2$ vertices? Or is a $1 \times 1$ grid a single point? I'm assuming the former.)

A $k \times k$ square will have an lower left hand vertex as $(x,y)$ and a upper right hand vertex at $(x+k, y+k)$ with the stipulation $0 \le x; 0 \le y; x+k \le n; y+k \le n$ or in other words: $0 \le x \le n-k; 0 \le y \le n-k$.

There are $n-k+1$ possible options for $x$ and $n-k+1$ options for $y$ so there $(n-k+1)^2$ $k\times k$ squares.

So the total number of squares is $\sum{k=1}^n(n-k+1)^2$. Let $j = n-k+1$ and we have #squares = $\sum_{j = n;j--}^1j^2 = \sum_{j=1}^n j^2 = \frac{n(n+1)(2n+1)}6$

Or to put it more simply.... A $k \times k$ square has a side of length $k$. There are $n-(k-1)$ ways to choose this side from the grid that is $n$ long so for squares of lengths $1,2, ...., n$ there are $n, n-1....., 1$ way to choose the horizontal side and $n, n-1,...., 1$ ways to choose the vertical sides. So there are $n^2, (n-1)^2,....., 1^2$ possible $1\times 1, 2\times 2, ...,n \times n$ squares. So there are $\sum k^2 = \frac{n(n+1)(2n+1)}6$ total squares.

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