Monday, June 11, 2012

How Many Squares on a Checkerboard?

One of the classic numerical puzzles is the question: How many squares are on a checkerboard?

The simplest answer is to get out a board and count. After about a minute, you'll find there are 64 squares, and if you pay close attention you'll find that 32 of them are red and 32 of them are black. Of course, if you think about it more you'll realize you could have saved yourself some time and simply counted the squares along one edge, and the squares along the other edge and multiplied. 8x8=64.

Unfortunately, this simple answer wouldn't qualify this question as a puzzle. The crux of the problem is the fact that there are many more squares when you start to consider squares bigger than the simple 1x1's you see.  There are of course, 2x2 squares, and 3x3, and the whole checkerboard itself is a big square.  Now you need to find how many of each of these sized squares there are, and add them all up.

At first glance, I usually count 16 2x2 squares, until I lift my artificial requirement that the squares can't overlap. Allowing for overlapping squares means that I can fit 7 2x2 squares along one edge, and 7 2x2 squares along the other edge, for a total of 7 times 7 = 49 squares.  Including the 1x1's I'm now up to a total of 64 + 49 = 113.

Thankfully, the remaining square sizes are just as easy to find, and I'll summarize them in the table below:
"1x1"s:  8 per edge * 8 per edge = 64 squares
"2x2"s:  7 per edge * 7 per edge = 49 squares
"3x3"s:  6 per edge * 6 per edge = 36 squares
"4x4"s:  5 per edge * 5 per edge = 25 squares
"5x5"s:  4 per edge * 4 per edge = 16 squares
"6x6"s:  3 per edge * 3 per edge = 9 squares
"7x7"s:  2 per edge * 2 per edge = 4 squares
"8x8"s:  1 per edge * 1 per edge = 1 square

Grand total then: 204 squares!

The pattern can be generalized and extended in a number of ways, only one of which I will discuss here. The generalization I will discuss is how many squares on a "checkerboard" of any size nxn. Further complications would be to allow for any rectangular shaped boards, and/or to ask for how many rectangles there are instead. And why limit the question to squares and rectangles? I've seen the question asked in various forms with triangular boards too.

So, how many squares are on a board of any (n x n) size?  Lets develop a pattern starting with the simplest cases and work up.

A 1x1 board would have just 1 square.
A 2x2 board would have 1 + 2² or 5 squares.
A 3x3 board would have 1 + 2² + 3² or 14 squares.

Continuing the pattern would show that an (NxN) board would have 1² + ... + N² squares on it. For small N's, this is easily calculated on a calculator by simply typing them up, but for larger checkerboards, it's easiest to use the formula:

Interestingly these numbers, 1, 5, 14 ..., 204, and so on are called the square pyramid numbers, so-named because it that's how many blocks are required to create square pyramids, like the displays of oranges in the store like the picture shown below:

How many oranges are in that picture? It appears there are 12 across the bottom row, which means we are asking the question: How many squares are there in a 12x12 checkerboard?  Using the formula above, that's (12)(13)(25)/6 = 650