Problem Solving Question

So it has been a while since my last post. I’m not going to lie, since school has picked up I find the slog constantly being pushed to the back of the line in terms of work priority. Hopefully I can continue to make more frequent posts.

For this post, I’ve decided to take a look at the sub-square problem from the problem-solving wiki:

Suppose you have a 3x3 grid. How many squares (1x1, 2x2, 3x3) are there whose corners correspond to grid intersections? Can you come up with a way of predicting how many sub-squares there are for an mxm grid, for an arbitrary choice of non-negative integer m?

Solution:
First, to try to find a distinct pattern, I found that it was beneficial to draw out each grid and see
how many sub-squares could fit on each square.

1x1 grid:     1 (1x1) sub-square

Total:          1


2x2 grid:     1 (2x2) sub-square
                    4 (1x1) sub-squares

Total:          5



3x3 grid:     1 (3x3) sub-square
                    4 (2x2) sub-squares
                    9 (1x1) sub-squares

Total:         14


4x4 grid:     1 (4x4) sub-square
                    4 (3x3) sub-squares
                    9 (2x2) sub-squares
                    16 (1x1) sub-squares

Total:          30


5x5 grid:      1 (5x5) sub-square
                     4 (4x4) sub-squares
                     9 (3x3) sub-squares
                     16 (2x2) sub-squares
                     25 (1x1) sub-squares

Total:           55

From what you can see above, there seems to be a pattern developing. The formula can be expressed like this:

Total number of sub-squares in an (m x m) grid = m^2 + (m-1)^2 + (m-2)^2 + .... + (m-m)^2 

So now we can check if this formula works for a 6x6 grid. I drew out the square and figured out that it should result in a total sub-square number of 91.

Now we substitute 6 with m in the formula from above:

(6)^2 + (5)^2 + (4)^2 + (3)^2 + (2)^2 + (1)^2 + (0)^2
= 36 + 25 + 16 + 9 + 4 + 1 + 0
= 91.

This now confirms that the formula checks out.