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.
