GO Classes Weekly Quiz 13 | Discrete Mathematics | Combinatorics | Question: 11

Answer 1

As in the comment,  @abhishek29 has mentioned a nice recurrence for the given problem. I am trying to explain how we can make this recurrence. If we get the recurrence, then we can get the answer easily because solving this recurrence is not difficult.

 

Finding newly added squares of sizes $1 \times 1, 2\times 2,...$ for each $T_i$ is not difficult at all. We just have to observe how many new squares of different sizes are creating each time when we add a new horizontal and vertical layer. Based on $T_3,T_4,T_5…,$ we can write:

$T_n = T_{n-1} + (n+ (n-1)) + ((n-1) + (n-2)) + ((n-2) + (n-3)) +….+1,$ for $n \geq 3$

($T_2$ is my base case here)

$T_n = T_{n-1} + n + 2((n-1) + (n-2) + ...+1)$

$T_n = T_{n-1} + n + 2 \frac{(n-1)n}{2}$ 

$T_n = T_{n-1} + n^2$

Comments

Nice approach.

Answer 2

Hints to get the answer:

• Step $1:$ There are more squares than the $64 \;(1 \times 1)$ squares.
• Step $2:$ Find out the number of $2 \times 2$ squares and so on up to $8 \times 8$ squares.
• Step $3:$ Add the result.

The number of squares on a chess board:

There are more squares in a chess board than the $64\;(1 \times 1)$ squares.

The squares start from $1 \times 1$ all the way up to $8 \times 8$.

Let us count them and find a way to add all of them.

1. $1 \times 1$ squares $-8$ squares across the width and 8 squares along the length $=8 \times 8=64$
2. $2 \times 2$ squares - with the size of the square increasing by $1$ square the number of squares across the width will be down to $7$ and the ones along the length will also be down to $7.$ So, there are $7 \times 7=49(2 \times 2)$ squares.
3. $3 \times 3$ squares $-6$ squares across the width and $6$ along the length $=6$ $\times 6=36(3 \times 3)$ squares.
4. $4 \times 4$ squares $-5$ squares across the width and 5 along the length $=5$ $\times 5=25(4 \times 4)$ squares.
5. $5 \times 5$ squares $-4$ squares across the width and 4 along the length $=4$ $\times 4=16(5 \times 5)$ squares.
6. $6 \times 6$ squares $-3$ squares across the width and $3$ along the length $=3$ $\times 3=9(6 \times 6)$ squares.
7. $7 \times 7$ squares $-2$ squares across the width and $2$ along the length $=2 \times$ $2=4(7 \times 7)$ squares.
8. $8 \times 8$ squares $-1$ square across the width and $1$ along the length $=1 \times 1$ $=1(8 \times 8)$ square.

Therefore, the total number of squares in a chess board = $64+49+36+25+16+9+4+1=204$ squares.

NOTE: If you figured that the number of squares is the summation of squares of natural numbers up to 8 , you could have used the formula $n(n+1)(2 n+1) / 6$, where $n=8$

Continuing in this way, we get squares of size $3 \times 3,4 \times 4$, and so on.
$$\begin{array}{ll}\text { Size of } & \text { Number of } \\ \text { Square } & \text { squares } \\ 1 \times 1 & 8 \times 8=64 \\ 2 \times 2 & 7 \times 7=49 \\ 3 \times 3 & 6 \times 6=36 \\ 4 \times 4 & 5 \times 5=25 \\ 5 \times 5 & 4 \times 4=16 \\ 6 \times 6 & 3 \times 3=9 \\ 7 \times 7 & 2 \times 2=4 \\ 8 \times 8 & 1 \times 1=1\end{array}$$

So there are $204$ squares.

Comments

I am not sure if this is correct way.

You have written a recurrence for the given problem. You can also verify it easily.  

“Here we observe a pattern that for say 3 square-shape we get $3^2$+(previous number of squares)”

It means you are writing a recurrence as:

$T_n = n^2 + T_{n-1}$ with $T_1 =1$

Here, $T_n$ is the number of squares of all sizes for a chessboard of size $n \times n.$

Now, if you solve it by back substitution, you get, $T_n = 1^2 + 2^2 + …+ n^2 = \frac{n(n+1)(2n+1)}{6}$

Now, you can use induction to verify it.

Could you explain how did you make the recurrence ? I mean, What’s are your thoughts to make this recurrence ? 

---

Oh yes recurrence it is. I just recognised the pattern like it's square plus previous term.

---

yes, nice. It is not possible for everyone to find patterns. I have added one of the possible explanations to construct the recurrence.

You can check here