2
$\begingroup$

Given a rectangle of length a and width b (as shown in the figure), how many different squares of edge greater than 1 can be formed using the cells inside.

enter image description here

For example, if a = 2, b = 2, then the number of such squares is just 1.

$\endgroup$
4
  • $\begingroup$ Are the interior cells squares? $\endgroup$
    – Jebruho
    Nov 4, 2012 at 21:25
  • $\begingroup$ Also, check your spelling. $\endgroup$
    – Jebruho
    Nov 4, 2012 at 21:26
  • $\begingroup$ @Jebruho:Interior cells are squares. $\endgroup$
    – g4ur4v
    Nov 4, 2012 at 21:28
  • $\begingroup$ @WillHunting:a and b can be different. $\endgroup$
    – g4ur4v
    Nov 4, 2012 at 21:29

3 Answers 3

2
$\begingroup$

In general, given an $n \times k$ grid of squares, to find the number of rectangles you can form, you would turn your grid into an $n \times k$ multiplication table, put the values into each square (i.e., the $i$th row and $j$th column would contain $i \cdot j$), and then sum them all up. Proving that this holds is a nice exercise.

For your particular question, you are asked to find the number of squares in a $3 \times 3$ grid where each square has its sides greater than $1$. This is straightforward to figure out directly from your picture (how many $3 \times 3$ squares are there? how many $2 \times 2$ squares are there?) but the solution also becomes clear to anyone who proves the statement of the previous paragraph.

The number of $3 \times 3$ squares is $1$, which is $1 \cdot 1$; the number of $2 \times 2$ squares is $4$, which is $2 \cdot 2$. Thus, the total is $1 + 4 = 5$.

Incidentally, the number of $1 \times 1$ squares is $9$, which is $3 \cdot 3$. Note that $1, 4, 9$ are the entries of the diagonal in a $3 \times 3$ multiplication table. This is no coincidence!

Given an $n \times n$ multiplication table, to find the number of squares, just add up all the elements of the diagonal. The formula for the sum of the first $n$ squares, by the way, is $n(n+1)(2n+1)/6$, which you could look up online or prove by induction.

Since you want to exclude $1 \times 1$ squares, you would subtract $n^2$ from this sum, giving a final answer of $$S(n) = \frac{n(n+1)(2n+1)}{6} - n^2 = \frac{(n-1)n(2n-1)}{6}$$

Indeed, for $n = 3$, we find $S(3) = 5$ as desired.

$\endgroup$
2
  • $\begingroup$ :This is great for when a=b=n.What about when a is not equal to b? $\endgroup$
    – g4ur4v
    Nov 4, 2012 at 21:53
  • $\begingroup$ Try to prove the statement from the first paragraph and see what sort of insights that gives you. Also, for a semi-related question, check out: math.stackexchange.com/questions/226983/… $\endgroup$ Nov 4, 2012 at 21:58
2
$\begingroup$

Without loss of generality we may assume that that the width $b$ is $\ge$ to the height $a$. Note that there are $b+1$ vertical lines and $a+1$ horizontal lines in the picture.

If $a\ge 2$, the number of $2\times 2$ squares is $(a-1)(b-1)$. This is because the top left corner of a $2\times 2$ square can be any corner that is not in the last two columns or the last two rows.

If $a\ge 3$, the number of $3\times 3$ squares is $(a-2)(b-2)$. This is because the top left corner of a $3\times 3$ square can be any corner which is not in the last three columns or the last three rows.

If $a\ge 4$, the number of $4\times 4$ squares is $(a-3)(b-3)$.

Continue. Finally, the number of $a\times a$ squares is (a-(a-1))(b-(a-1))$.

Add up. To get a "nice" expression for the sum, note that $$(a-k)(b-k)=ab-k(a+b)+k^2.\tag{$1$}$$

When we add up the expressions in $(1)$, we get $a-1$ terms with value $ab$, for a total of $(a-1)ab$.

The "middle" terms add up to $-(a+b)(1+2+\cdots+(a-1))$. The sum is $-(a+b)\dfrac{(a-1)a}{2}$.

Finally, we need $1^2+2^2+\cdots +(a-1)^2$. By the usual formula for the sum of consecutive squares, this is equal to $\dfrac{(a-1)(a)(2a-1)}{6}$.

$\endgroup$
-4
$\begingroup$

In an $n\times p$ rectangle, the number of rectangles that can be formed is $\frac{np}{4(n+1)(p+1)}$ and the number of squares that can be formed is $\sum_{r=1}^n (n+1-r)(p+1-r)$.

$\endgroup$
2
  • 1
    $\begingroup$ Why $n \times p$ instead of $a \times b$ as in the question? $\endgroup$ Aug 21, 2016 at 7:55
  • 3
    $\begingroup$ While this answer gives a little bit of an idea how to solve the question, it does not contain enough detail to merit answering an almost 4-year old question. And it is not formatted properly. $\endgroup$ Aug 21, 2016 at 7:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .