Question

The Blade Dancer

So how exactly can we apply this method to another problem of similar requirements but of a larger dataset, say 10 x 10?

thomas

@The-Rogue-Blade Great question! If you've understood what Proffesor Loh meant by a "pattern", I think it can be pretty easy to figure out how you might do something very similar for a $10 \times 10$ grid.

In the original question with the $4 \times 4$ grid, we figured out that the answer was:
$$1 \times 3^2 + 2 \times 2^2 + 3 \times 1^2$$
This is because each of these terms comes from a different case:

Inside each $1 \times 1$ bounding box, there is only $1$ square that can be made. There are $3 \times 3$ bounding boxes. So, there are $1 \times 3^2$ squares with a $1 \times 1$ bounding box.
Inside a $2 \times 2$ bounding box, you can actually find $2$ squares you can make by connecting points along the border of the box. And, you can count that there are $2 \times 2$ of these $2 \times 2$ bounding boxes, so we count $2 \times 2^2$ squares in total for this case.
Lastly, for a $3 \times 3$ bounding box, there are $3$ squares you can make by connecting points on the edge of the box. And, there's only one of these bounding boxes, so we have $3 \times 1$ from this case.

The pattern is pretty clear: When we increase the size of the bounding box by one, the number of squares that I can find inside it also increases by one. But, if there were $n^2$ of those bounding boxes before I increased the size, then there will be only $(n-1)^2$ of those bounding boxes if I make them one bigger. This is where that $1,2,3$ and $3^2,2^2,1^2$ pattern comes from.

Now let's try to use this for a $10 \times 10$ grid of dots! It looks like this:

One thing to be careful of before we start: This is a $10 \times 10$ grid of dots, but the "square" that it forms is actually a $9 \times 9$ square, just like how a $2 \times 2$ grid of dots forms a simple $1 \times 1$ square. We should keep this mind so we don't run into any silly mistakes from being off-by-one. Now let's start!

If you're not sure how to immediately apply that pattern from before, let's start simple with a few cases:

Like before, there is only $1$ square in a $1 \times 1$ bounding box. How many $1 \times 1$ bounding boxes are there? Ah, there are $9 \times 9$ of them. So in this case there are $1 \times 9^2$ of these squares.
As before, there are $2$ squares in a $2 \times 2$ bounding box. How many $2 \times 2$ bounding boxes are there? If you think about it, you can find $8 \times 8$ of them (make sure you see why!). So there are $2 \times 8^2$ squares in this case.

Hmm... So far I have the terms:
$$1 \times 9^2 + 2 \times 8^2 + \cdots$$
You know what, I think I see the pattern! Can you guess the rest?

I'm pretty sure the rest of this will look like:
$$1 \times 9^2 + 2 \times 8^2 + 3 \times 7^2 + 4 \times 6^2 + 5 \times 5^2 + 6 \times 4^2 + 7 \times 3^2 + 8 \times 2^2 + 9 \times 1^2$$
I think that's the answer! But before I get too carried away, I need to make sure that this sorta makes sense. This is what I call a "sanity check", meaning that I just want to make sure my reasoning is realistic. The way I could check that this answer makes sense is by looking at the last term: $9 \times 1^2$. I should make sure that this indeed is the number I would get if I count all the squares in the last case. What is the last case? That would be counting all the squares along the border of the $9 \times 9$ bounding box. Aha! That makes sense, because there would be $9$ squares in a $9 \times 9$ bounding box, and there is only one such bounding box, hence it makes sense that the last term is $9 \times 1^2$. I think we're in the clear!

Finally, once we sum up all those numbers in that big expression above, we'll get a whopping $\boxed{825}$ squares.

Now, that's pretty hard to do by hand! Personally, I used a calculator to make sure I multiplied and added all those numbers correctly. But, I wonder if there's a way to do this if there is... a $100 \times 100$ grid of dots? We can always use the pattern to make a big expression like we did that would add up to the correct answer, but how can we multiply and add all those numbers up by hand without messing up?

To figure that out, we have to do something pretty cool: We need to find a formula. What do I mean? Let's say that there is an $n \times n$ grid of dots. What is the formula for how many squares there are in that grid of dots, in terms of $n$? I think that's a really exciting question! If you can figure out what the formula is, you don't need to compute the number of squares by hand anymore, and you can just plug it in.

This is often what mathematicians really like to do: If they can solve some specific cases of a problem, they often want to generalize it, or solve it for all the possible cases by making a formula.

I'll leave that for you to think about. Do tell us if you can figure out what the formula is!

The Blade Dancer

If someone can put this into stuff people can understand, that'd be great, but I'm not very good with code. So I'm just going to describe it.

n = size of one dimension in square grid
x = number of possible combinations in bounding box
y = number of bounding boxes

To find number of combinations in any given grid,
start with the highest size bounding box possible, in which possibilities will equal $$ y \times n^2 $$

For the next bounding box size, increase y by 1 and decrease n by 1. So like this:

$$ y+1 \times (n - 1)^2 $$

Keep adding and subtracting from one side until n = 1. Then, add all the products up.