Counting squares in a given k by k square..

854 Views Asked by At

So the question is :

enter image description here

The solution to this problem according to the book is to first count the number of squares whose sides are parallel to the sides of this 10 by 10 square and then to count the squares whose sides aren't....

For e.g., there are 8 x 8 2 by 2 quartets, and 7 x 7 3 by 3 quartets and so on....

so the general equation for counting these squares is $(10 - k)^2$ k by k squares.

and for counting the other squares whose sides aren't parallel to the main square, there are $k$ k by k squares inscribed in a k by k square including the quartet itself.

So the solution goes proceeds to sum these number of squares, and the final answer is something like this:

enter image description here

But by doing that, didn't they double count the quartets because while counting the inscribed squares, they counted the quartet itself too?

Instead of this:

enter image description here

shouldn't it be something like sum of $(10 - k)^2 * (k - 1)$ from 1 to 9?

1

There are 1 best solutions below

2
On

The argument for axis aligned squares is correct: there are $(10-k)^2\ k \times k$ such squares, so the total number is $\displaystyle \sum_{k=1}^9 (10-k)^2=\sum_{k=1}^9 k^2=\frac {9(9+1)(2\cdot 9+1)}6=285$ of them.

The logic of the non-axis aligned squares is not correct. There are no $k \times k$ non-aligned squares in a $k \times k$ square. For $\sqrt 2 \times \sqrt 2$ squares, the leftmost corner can be any of $8 \times 8$ points (not the top or bottom rows and not either of the right two columns). The easiest way to count them is to find the axis-aligned square that bounds them. If the lower left side goes down $m$ and rightward $n$ units, it fits in an $(m+n) \times (m+n)$ square. As long as we insist $m,n \gt 0$ we won't double count any aligned squares. So we get $$\sum_{m=1}^8\sum_{n=1}^{9-m}(10-m-n)^2$$ of them