Wednesday, June 10, 2015

Counting squares in a grid using the sum of squares method


A while back a colleague asked some of us how we would go about solving a particular Mathematical problem. The problem was to count the total number of squares in a Chess board. This included all squares of size 1x1, 2x2, up to 8x8.

I found a number of different ways of solving the problem which I'm going to present in the next few blog posts.

As has been the theme with my previous blog posts on Mathematical puzzles, my goal is to progress from solutions which are algebraic to solutions which provide insight.

This blog post is about the first way of solving the problem, which I've dubbed the sum of squares method.

Note that I'll be solving the problem for any n x n grid (or lattice), not just for the 8 x 8 chessboard.

All posts in this series

Step 1: How many k x k squares fit into an n x n grid?

Supposing we have an n x n grid. In how many different ways can we fit a square of size k x k into the grid (and of course its edges must align with edges inside or along the edge of the grid)?

Consider the k x k pink square shown in the diagram below...

I've shown the top-left cell of the pink square in a darker pink. We can't move the dark pink square any further right or down. But we could move it up or to the left. As we move the square around, the dark pink cell can end up anywhere within the yellow area.

So the number of possible positions for the pink k x k square is precisely the number of positions for the dark pink cell, which is the size of the yellow area.

Now the yellow area has sides of length: $n - (k - 1) = n - k + 1$. So there are $(n - k + 1)^2$ possible k x k squares that can fit into the n x n grid.

Step 2: Add up the number of squares for each value of k

The smallest value of k is 1 and there will be $n^2$ one-by-one squares fitting in the grid. The largest value of k is n and there will be only one n x n square.

If we add up the number of k x k squares for each value of k we get a formula of:

$$ \sum_{{k}={1}}^{n}(n - k + 1)^2 $$
That's quite a neat formula. But we can make it even neater by adding a new variable $i = n - k + 1$ and summing over all possible values of $i$ instead. The following table will make this clearer:

$k$ $i = n - k + 1$ Number of squares of size k x k
$ = (n - k + 1)^2 = i^2$
$1$ $n$ $n^2$
$2$ $n - 1$ $(n-1)^2$
... ... ...
$n - 1$ $2$ $2^2$
$n$ $1$ $1^2$

Now instead of summing over the values of k (from top to bottom), we can instead sum over the values of i (i.e. starting from the bottom row to the top row). And our formula becomes: $$ \sum_{{i}={1}}^{n}i^2 $$

Step 3: Derive a closed form solution

The formula above is very succinct and beautiful. But it has a drawback... as $n$ gets large, it's going to a take a long time to do all those summations. To address this, what we really want to find is a closed form solution without any summation symbols.

In future posts I'm going to show you a few different ways of getting a closed formula.

Next steps...

In the next blog post in this series, I'm going to derive the closed form solution through algebraic manipulation of the summation formula.

In later posts I will derive the number of squares in the grid in other ways. These will lead directly to the closed form solution. I'm hoping they will also give more insight into why the formula comes out the way it does.

No comments: