The chessboard is an inessential detail, so let's re-phrase the question:
How many squares, of any size, are there on an 8x8 grid?
Eventually, it'll be:
How many squares, of any size, are there on an n x n grid?
Some tools that I'll be using to solve this problem:
- Sequences
- Basic arithmetic
- A nifty property of sequences called Δ-k constants and which help us find "closed" formulas (more on that later)
As is common in problem solving, the simplest examples illustrate the problem and give a starting point.
A 0x0 grid
There are zero squares of any size.
A 1x1 grid
There is one square of size 1x1.
A 2x2 grid
This is where the "of any size" bit takes on meaning. In a 2x2 grid there are actually 5 squares "of any size." This is because a 2x2 grid contains 4 1x1 squares and then a single square of size 2x2.
You can see here that there are 5 squares of multiple sizes. There are four 1x1 squares and then a 2x2 square (the dashed-square). There are 4 + 1 = 5 total squares.
A 3x3 grid
A 3x3 grid is nothing but nine 1x1 squares, four 2x2 squares, and one 3x3 square. I've highlighted one of the four 2x2 squares (they contain numbers 1,2,4,5). There are 9 + 4 + 1 = 14 total squares.
A pattern emerges
Enter sequences:
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order does matter
Let's write the total number of squares as a sequence. The "index" of each item in the sequence represents n in the n x n grid:
0, 1, 5, 14
Each element in our total number of squares sequence can be defined as a the sum of all previous totals up to, and including, the current total. Put another way:
0x0 -> 0 squares (0)
1x1 -> one 1x1 square + zero 0x0 squares (1 + 0)
2x2 -> four 1x1 squares + one 2x2 square + zero 0x0 squares (4 + 1 + 0)
3x3 -> nine 1x1 squares + four 2x2 squares + one 3x3 square + zero 0x0 squares (9 + 4 + 1 + 0)
If n = 3, the number of squares on your n x n grid is: 01 + 12 + 22 + 32 or 0 + 1 + 4 + 9 = 14.
Answering our original question is now easy.
How many squares of any size are there on an 8x8 grid?
You just sum the squares from 0 to n.
sum([i**2 for i in range(0, 9)]) # 204
Recall that range counts from 0 up to 9, but not including 9.
Finding a closed formula
We can find a closed formula to calculate this without the summation. For example, you could add all the terms of a sequence of 1, 2 ,3, ..., n to find the total. Or your could use this handy equation:
total = (n(n+1)) / 2
Compare: 1+2+3+4+5 = 15 and (5(5+1))/2 = 15.
Let's take our sequence and extend it with a few more elements:
1, 5, 14, 30, 55
We can find a pattern of sorts by taking the differences between terms. We can form another sequence of terms (the differences) which will always be one element shorter than the original.
1, 5, 14, 30, 5
4, 9, 16, 25
5, 7, 9
2, 2
We took differences three times in order to reach a constant. What we just did there was find the Δ-k constant. In this case, Δ3 constant.
This is important for this reason:
The closed formula formula for a sequence will be a degree k polynomial if and only if the sequence is Δk-constant
This means our closed formula will be a degree k (3) polynomial or:
an = an3 + b2 + cn + d
Note: an represents the nth element of a, which is our sequence: 0, 1, 5, 14, 30, 55. The 0th term is 0, the 1st term is 1, the second term is 5, etc.
a0 = 0 = a(0)3 + b(0)2 + c(0) + d
The above simplified to: d = 0—an important piece of information.
a1 = 1 = a(1)3 + b(1)2 + c(1) + 0
a1 = 1 = a + b + c
a2 = 5 = a(2)3 + b(2)2 + c(2) + 0
a2 = 5 = 8a + 4b + 2c
a3 = 14 = a(3)3 + b(3)2 + c(3) + 0
a3 = 14 = 27a + 9b + 3c
Now we have a system of equations which we can solve for to get the values of a, b, and c.
a1 = 1 = a + b + c
a2 = 5 = 8a + 4b + 2c
a3 = 14 = 27a + 9b + 3c
To save time, I will wave my hand and solve that system:
a = 1/3
b = 1/2
c = 1/6
With these values, we now have our closed formula:
an = 1/3(n)3 + 1/2(n)2 + 1/6(n)
If n = 8: 1/3(8)^3 + 1/2(8)^2 + 1/6(8) = 204
If n = 800: 1/3(800)^3 + 1/2(800)^2 + 1/6(800) = 170986800
Top comments (0)