Expert: Paul Klarreich - 12/10/2006

Question
Hi, i need help with a math IB school project. I am looking or help developing an algebraic formula to find the solution to this problem. First, using just 11 lines to form a grid (either 1x10,2x9,3x8,4x7 etc), one can count the total number of squares inside the grid. The number of squares must however include the number of 1X1 squares, 2X2 squares, 3X3 squares, etc. The squares may overlap each other.

Then after that, i must look to see if there is a pattern in other patterns using, for example, 12 or 13 lines instead 11. I need to find out if there is a formula possible for finding the total number of squares (of all sizes) in relation to the number of lines total, and the number of lines height-wise and lengthwise. I have heard somewhere that this one requires some calculus.

I appreciate any help you will give me on this project. Thank you so much,
    Jordan Deeks.

Answer
Questioner:  Jordan
Category:  Advanced Math
 
Subject:  
Question:  Hi, i need help with a math IB school project. I am looking or help developing an algebraic formula to find the solution to this problem. First, using just 11 lines to form a grid (either 1x10,2x9,3x8,4x7 etc), one can find the total number of squares inside the grid. The number of squares must however include the number of 1X1 squares, 2X2 squares, 3X3 squares, etc. The squares may overlap each other.

Then after that, i must look to see if there is a pattern in other patterns using, for example, 12 or 13 lines instead 11. I need to find out if there is a formula possible for finding the total number of squares (of all sizes) in relation to the number of lines total, and the number of lines height-wise and lengthwise. I have heard somewhere that this one requires some calculus.

I appreciate any help you will give me on this project. Thank you so much,
   Jordan Deeks.
......................................
Hi, Jordan,

This sounds as if it's a big project, and I don't know where it's going, but I can make a couple of suggestions.  (And it does NOT look like a calculus problem to me, rather a combinatorial one.)

There are a couple of things that are not so clear, but we may be able to get around them.  

How do you form your grid using 'just 11 lines?'  That is not clear at all.  Your 1X10 grid, for example, looks like this, I assume: (USE A FIXED FONT TO VIEW IT.)

+-+-+-+-+-+-+-+-+-+-+
| | |3| | |6| | |9| |
+-+-+-+-+-+-+-+-+-+-+

(numbers inserted just for counting purposes.)

That looks like 11 vertical lines and 2 horizontal lines, or 13 total.

And your 3x8 grid would look like:

+-+-+-+-+-+-+-+-+
| | |3| | |6| | |
+-+-+-+-+-+-+-+-+
| | |3| | |6| | |
+-+-+-+-+-+-+-+-+
| | |3| | |6| | |
+-+-+-+-+-+-+-+-+

That's 9 vertical, 4 horizontal, also 13.

But leave that aside for now.  Suppose you have a grid that is, say, 3x8.  How many internal squares does it have?

Size 1:  3 * 8
Size 2:  2 * 7
Size 3:  1 * 6
----------------
Total :  3*8 + 2*7 + 1*6

How can we make a pattern out of that?  Write expressions that are systematic and use the original numbers, perhaps something like:

Size 1:  3-0 * 8-0
Size 2:  3-1 * 8-1
Size 3:  3-2 * 8-2
-------------------
Total :  see below.

Then write it in the 'standard' summation form, using a dummy variable.  In this, you see that the 3 and 8 remain the same, and other numbers go from 0 to 2.  Call those other numbers something like 'k', and write:

Size k:  3-k * 8-k
and k goes from 0 to 2.

   2
Summation  (3 - k)(8 - k)
 k = 0

Do some algebra on that:

   2
Summation [24 - 11k + k^2]
 k = 0

Next, look up some formulas for summations of integers, like:

  n          n(n+1)
Summation k = ------       [SUM 1 FORMULA]
 k=0           2

  n            n(n+1)(2n+1)
Summation k^2 = ------------   [SUM 2 FORMULA]
 k=0                6

Put those in and work out the algebra.  Of course, you will get some constants, which don't help you much at this stage, but at least you know how the process works.

So the next thing is to observe that the summation goes from zero to two because it can't be more than one less than the smaller dimension.  For example, if you had a  23x58 grid to start with (I won't draw it), your summations would look like:

Size 1:  23-0 * 58-0
Size 2:  23-1 * 58-1
Size 3:  23-2 * 58-2
.................
Size k:  23-k * 58-k
-----------------
Size 23: 23-22 * 58-22

Total is:

   22
Summation  (23 - k)(58 - k)
 k = 0

Now you realize that if the grid had sizes designated by symbolic numbers, let's call them M and N, with M the smaller, the summation would look like:

Size 1:  M-0 * N-0
Size 2:  M-1 * N-1
Size 3:  M-2 * N-2
.................
Size k:  M-k * N-k
-----------------
Size 23: M-(M-1) * N-(M-1)

We're getting there:

  M-1
Summation  (M - k)(N - k)
 k = 0

  M-1
Summation  [MN - (M+N)k + k^2]
 k = 0

Now you can use those SUM 1 and SUM 2 formulas above, putting n (little n, that is -- don't mix up big and small letters here) equal to  M-1 in both, doing a little algebra (OK, more than a little) and working out a formula in terms of M and N.

I'll stop here.  After all, it's your project.