2010/04/13

Answer to Squares Question

Given a grid that is NxN, how many squares can you make by connecting the dots?

The answer I got is this:



The reason is pretty neat. For an example, let's use a 5x5 grid.



Here is the sum:

1 * (5 − 1)2 + 2 * (5 − 2)2 + 3 * (5 − 3)2 + 4 * (5 − 4)2

Which equals:

1 * 16 + 2 * 9 + 3 * 4 + 4 * 1

Let's start with the first term: 1 * 16. When you have a 2x2 matrix, you can make 1 square. And in a 5x5 matrix, you can make 16 of those squares.



Next is 2 * 9. In a 3x3 matrix you can make 2 squares (as below) and there are 9 places you can do this in a 5x5 matrix.



This continues for 3 * 4 as there are 4 places you can make the 3 squares below.



And finally, you can make 4 squares out of the largest block just one time in a 5x5 square.



I thought this was really interesting and elegant. So the next thing I did was figure out the answer for any matrix of NxM. It is actually pretty simple. The answer for the NxN matrix was the sum of x(N-x)^2 because N-x was the area.. so with an NxM matrix the sum is like this:

2 comments:

Mark said...

I love Math. I just wish I could understand it the first time.

Your game with this seems like a pretty cool idea. Something people could have fun with.

Kai said...

Great, very nice answer. Wish I would have come up with this. Is there a formal proof?