Simple Maths Problem

Post Reply New Topic

Hey there. I've found a maths problem and want to know (a) if anyone has discovered it before I have & (b) what the answer is.

The problem is simple,


A square with one side is one square. A square with two by two sides is 4 squares, plus one imaginary square (the square around the outside which supervenes on the other four).



A square with 3 sides contains 9 squares and 5 supervening squares (or 'imaginary' squares). This is 14 squares in total.

If we take the length of the side of a square to be n, the number of real squares to be r and the number of supervening squares to be s, then the number of total squares (t), is equal to r+s.

[u]n r s t[u/]
1 1 0 1
2 4 1 5
3 9 5 14
4 16 14 30
5 25 30 55
6 36 55 91

Clearly a pattern has emerged, and is predictable. Someone already have me a formula involving sum, (the sigma symbol, I don't remember the exact solution). However, a sum doesn't work if n is huge, or at least a large sum is unsatisfying if n is huge. I wonder, since the pattern is so clear, if anyone can come up with a formula which will work with any n and won't require 2 hours work if n is 3,000.
One method which seemed productive was to count the number of 2x2 supervening squares and mark them down separately from the 3x3 supervening squares. I remember more patterns emerging, but I still can't get anything into a concise formula.


I know almost nothing about maths, so please explain any technical terms more complicated than multiplication.

Further, my BBCode seems not to be working. Why is this?
[Mod. edit: you'd quoted the filename]

First of all, (as you may have already noticed), the number of 1x1 squares in an NxN grid is the same as the number of 2x2 squares in an (N+1)x(N+1) grid.
Generalise this to see that the total number of squares in an NxN grid, plus the number of 1x1 squares in an (N+1)x(N+1) grid, is equal to the total number of squares in that (N+1)x(N+1) grid.

This is quite obvious from the pattern you quoted, and that's also where the summation answer comes from:
The sum, for 1 <= n <= N, of n^2.

The difficult part is to make this into a single formula. Now, some maths intuition tells me that it's probably a cubic function. (A real mathematician can probably say that for sure).
Cubic functions are of the form An^3 + Bn^2 + Cn + D
If that is indeed the form, then all that is left is to solve it. One way to do that is to fill in some known values for n (n=0, 1, 2, 3 for example)
For n=0, the result is 0, so A*0 + B*0 + C*0 + D = 0, so D = 0.
For n=1, the result is 1, so A*1 + B*1 + C*1 = 1, so A + B + C = 1
For n=2, it's 5, so A*8 + B*4 + C*2 = 5
And for n=3, A*27 + B*9 + C*3 = 14

Solving this for A, B, C is a tedious process:
C = (1-B-A)
A*8 + B*4 + (1-B-A)*2 = 5
A*8 + B*4 + 2 - B*2 - A*2 = 5
A*6 + B*2 + 2 = 5
A*6 + B*2 = 3
A*3 + B = 1.5
B = (1.5 - A*3)
A*27 + (1.5 - A*3)*9 + (1-(1.5 - A*3)-A)*3 = 14
A*27 + 13.5 - A*27 + 3 - (1.5 - A*3)*3 - A*3 = 14
A*27 + 13.5 - A*27 + 3 - 4.5 + A*9 - A*3 = 14
A*6 + 12 = 14
A*6 = 2
A = 1/3
(1/3)*3 + B = 1.5
1 + B = 1.5
B = 0.5
1/3 + 0.5 + C = 1
C = 1 - 1/3 - 0.5
C = 1/6

So, the formula is: 1/3n^3 + 1/2n^2 + 1/6n

Let's see if it works for larger n:
1/3*64 + 1/2*16 + 1/6*4 = 30
1/3*125 + 1/2*25 + 1/6*5 = 55

Looks like we have a winner.

Nice work. The formula is usually written in the form:



(N.B. the above image is editable, if you grab: http://www.thrysoee.dk/laeqed/)

Note that it is easy to see that the denominator must contain a factor of two, as either n or n+1 must be even. It must also contain a factor of three, as one of 2n, 2n+1 and 2n+2 must be a multiple of three. Hence the division by six is always going to yield an integer result.



P.S. Thanks for reminding me that the number of squares on a chess board is 204.

P.P.S. The sum of the plain "i" sequence is "n(n+1)/2". I always found it curious than the sum of i^3 is the same, but squared:
0 1 2 3 4 5
0 1 3 6 10 15

0 1 8 27 64 125
0 1 9 36 100 225
i.e.
0 1^2 3^2 6^2 10^2 15^2

It's all very provable, but it is just a mathematical coincidence. There's no underlying reason why the sum of the cubes of the natural numbers should be the square of their linear sum.

Anyway... a Rubic's Cube (3x3x3) contains (1+2+3)^2=36 cubes.

Cheers for the help guys. It's going to take me a while to understand all of that, but I shall.

And Thanks to the Moderator for the BBCode help.