Aptitude Overflow

+3 votes

Best answer

This is a 8x8 chessboard

We can clearly see that it consists of **8 Rows & 8 Columns**. And 8 Rows & 8 Columns result in **9 Horizontal Lines & 9 Vertical Lines**.

To form a rectangle we have to **select 2 Horizontal lines** out of 9 Horizontal lines **&** **2 Vertical lines** out of 9 vertical lines.

So, total number of rectangles Iin this 8x8 chessboard = ^{9}C_{2} * ^{9}C_{2}

0 votes

Suppose a block of 1 x 1,

How many squares it can form?

Only 1

But if we increment by 1 (2 x 2)?

4 (1 x 1) and 1 (2 x 2 ) = 5 squares

and similarly for 3 x 3 there are 1 square (3 x 3), 4(2 x 2) and 9 (1 x 1)

total 1 + 4 + 9 = 14 squares

We can form a recurrence relation,

T(n) = T(n-1) + n^{2}

T(3) = T(2) + 9 = 5 + 9 = 14

but what about T(8)? we need T(7) for that and hence we need a closed formula

which is nothing but

T(n) = $n^{2} + (n-1)^{2} + (n-2)^{2}+ ....+ 2^{2} + 1^{2}$ = $\frac{n(n+1)(2n+1)}{6}$

T(8) = $\frac{8(8+1)(16+1)}{6}$ = $12 * 17$ = 204

2,821 questions

1,230 answers

483 comments

40,337 users