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:

2010/04/08

Squares

The first (and only) program I ever made in Visual Basic was a game called Squares. I was in high school at the time, and didn't even know C, so I just wanted to make something simple and interactive.

In Squares, you have an 8 by 8 grid like a chess board. Players take turns putting their pieces on the board. When their pieces make a square, they get points equal to the area of the square. The game is tricky because squares can be rotated at any angle and are often hard to see. It's quite fun.. I made a simple hotseat version in canvas a while ago to test out canvas (Rendering shadows is slow!). Let me know if any of you are interested and I can show you the game.. if there is enough interest I could make it multiplayer online.

On a 2x2 board, there would only be one possible square. On a 3x3 board, you can make 6 squares.



So the question is, how many can you make on an 8x8 board? How about an NxN board? Or better yet.. an NxM board?? Anyone? :) It actually works out to be a nice clean answer.