Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

enter image description here

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

share|improve this question
    
Are the interior cells squares? –  Jebruho Nov 4 '12 at 21:25
    
Also, check your spelling. –  Jebruho Nov 4 '12 at 21:26
    
@Jebruho:Interior cells are squares. –  g4ur4v Nov 4 '12 at 21:28
    
@WillHunting:a and b can be different. –  g4ur4v Nov 4 '12 at 21:29

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
:This is great for when a=b=n.What about when a is not equal to b? –  g4ur4v Nov 4 '12 at 21:53
    
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/… –  Benjamin Dickman Nov 4 '12 at 21:58

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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