Maxium number of squares

[jbsdad]

I am trying to determine what is the maxium number of squares determined by a 7 x 7 figure? What is the formula/solution?

 

[pka]

I am trying to determine what is the maxium number of squares determined by a 7 x 7 figure? What is the formula/solution?

The statement is not well-defined.
If you give us a positive integer, then we can tell you how to construct at least that many squares in a 7x7 grid.

So you had best give more details about this question.

 

[mmm4444bot]

Hello JB's Dad:

We can't see your 7x7 "figure", but I'm guessing that it's a grid, like a chess board (8x8) or Tic-Tac-Toe board (3x3).

Did JB try drawing any pictures or conducting any experiments with smaller grids? This would be the way to go, if JB is looking for a pattern that would allow writing a "formula".

For example, with a 1x1 grid, there is only one unique square.

With a 2x2 grid, we can form a total of five unique squares. (Four of them are 1x1, and one of them is 2x2.)

With a 3x3 grid, we can form a total of 14 unique squares. (Nine of them are 1x1, four of them are 2x2, and one of them is 3x3.)

With a 4x4 grid, we can form a total of 30 unique squares. (16 of them are 1x1, nine of them are 2x2, four of them are 3x3, and one of them is 4x4.)

In other words, here are the total number of squares, as a function of the grid dimensions.

1x1: 1

2x2: 1 + 4 = 5

3x3: 1 + 4 + 9 = 14

4x4: 1 + 4 + 9 + 16 = 30

Does JB see a pattern?

If you're having difficulty visualizing the various-sized smaller squares within a larger grid, then you and JB might also find THIS SITE helpful.

If the original exercise deals with something else, then I've misunderstood your post. You'll need to provide a better description.

Cheers,

~ Mark

 

[TchrWill]

I am trying to determine what is the maxium number of squares determined by a 7 x 7 figure? What is the formula/solution?

A popular recreational mathematics puzzle is how many squares are there on a standard chess board? It is obvious that it is asking for not only the 64 basic playing squares but all the other definable squares made up of multiples of the smaller playing squares. The answer is not immediately obvious and requires some detective work to zero in on the actual number. The ultimate version of this problem would be how many identifiable squares or rectangles are formed by m horizontal rows and n vertical columns within a given square or rectangle? Lets see what we can learn.

There are four different scenarios that are possible from this question; the number of squares within a square, the number of rectangles within a square made up of the smaller squares, the number of squares within a rectangle made up of squares, and the number of rectangles within a rectangle. Obviously, in the case of squares within a rectangle, the dimensions of the rectangle must be a multiple of the side of the square. To break the ice, lets explore the simplest case of N squares within a square first where m = n.

For this basic case, lets define each outer square by the total number of squares, n, in each direction.
If you determine the number of squares, N, with smaller n's (fewer squares) starting with one square you will readily discover a pattern that leads to a simple formula for a board of any number of squares.
2x2 lines/1x1 square-A one square board obviously has only one square.
3x3 lines/2x2 square-A 2x2 square board has 5 squares, the 4 basic ones and the one large 2x2 one.
4x4 lines/3x3 square-A 3x3 square board has 14 squares, the small 9 plus 4 2x2's plus 1 3x3 one.
5x5 lines/4x4 square-A 4x4 square board has 30 squares, the small 16 plus 9 3x3's, plus 4 2x2's plus 1 4x4 one.

Are you beginning to see the pattern?
..n
1x1 - N = 1^2 = 1
2x2 - N = 2^2 + 1^2 = 5.
3x3 - N = 3^2 + 2^2 + 1^2 = 14.
4x4 - N = 4^2 + 3^2 + 2^2 + 1^2 = 30.
5x5 - N = 5^2 + 4^2 + 3^2 + 2^2 + 1^1 = 55.

What would your guess be for the number of squares on an 8x8 board? Lets see if we can derive a general expression for the answer?

Let N = the total number of squares in a square of nxn squares or (n+1)x(n+1) lines. Then

N = n^2 + (n-1)^2 + (n-2)^2................(n-n+1)^2 = 1^2+2^2+3^2+.....+n^2 = n(n+1)(2n+1)/6.

So for the typical chess board problem with 8x8 squares, the total number of definable squares is

N = 8^2 + 7^2 + 6^2 + 5^2 + 4^2 + 3^2 + 2^2 + 1^2 = 8(9)17/6 = 204

Another way of deriving the general expression is by recognizing that the data forms a finite difference series from which a general expression is derivable. Lets see how.

n..................1.....2.....3.....4.....5.....6.....7.....8
N squares.....1....5.....14...30...55...91..140..204
1st Diff............4.....9.....16...25...36...49....64
2nd Diff..............5......7.....9....11...13....15
3rd Diff..................2.....2......2.....2.....2

Therefore, we have a finite difference series ending in the constant difference of 2. An expression can be derived enabling the definition the nth term of any finite difference series. The expression is a function of the number of successive differences required to reach the constant difference. If the first differences are constant, the expression is of the first order, i.e., N = an + b. If the second differences are constant, the expression is of the second order, i.e., N = an^2 + bn + c. Similarly, constant third differences derive from N = an^3 + bn^2 + cn + d.
Our case will derive from N = an^4 + bn^3 + cn^2 + dn + e.

With the 3rd differences being constant, our expression takes the form of N = an^3 + bn^2 + cn + d.

Using the data points (n1, N1), (n2,N2), (n3,N3), etc., we substitute them into N = an^3 + bn^2 + cn + d as follows:

For (n1,N1) = (1,1) we get a(1^3) + b(2^2) + c(1^1) + d = a + b + c + d = 1
For (n2,N2) = (2,5) we get a(2^3) + b(2^2) + c(2^1) + d = 8a + 4b + 2c + d = 5
For (n3,N3) = (3,14) we get a(3^3) + b(3^2) + c(3^1) + d = 27a + 9b + 3c + d = 14
For (n4,N4) = (4,30) we get a(4^3) + b(4^2) + c(4^1) + d = 64a + 16b + 4c + d = 30

The solution of these four expressions leads us to a = 1/3, b = 1/2, c = 1/6, and d = 0 resulting in our general expression of N = [2n^3 + 3n^2 + n]/6 = n(n + 1)(2n + 1)/6.


Now lets consider the more challenging problem of how many rectangles there are in a square nxn squares or (n+1)x(n+1) lines big? We count only "rectangles", not the squares which are special cases of rectangles. Remember, only rectangles where the length is longer than the width.

One way to creep up on a solution is to start out with the small size squares and see where it leads you. For a 2x2 square, we have a total of 4 possible rectangles, each 1x2 squares. For the 3x3 square, we can find 12 1x2 squares, 6 1x3 squares, and 4 2x3 squares for a total of 22 squares. For the 4x4 square, we can find 24 1x2's, 16 1x3's, 8 1x4's, 12 2x3's, 6 2x4's, and 4 3x4's for a total of 70 squares. For the 5x5 square, we get 40 1x2's, 30 1x3's, 20 1x4's, 10 1x5's, 24 2x3's, 16 2x4's, 8 2x5's, 12 3x4's, 6 3x5's, and 4 4x5's.

Did you notice anything as you looked through these numbers? Lets put them into a tabular form. Along side each nxn square will be the number of squares identified at the top of the column.
1x2 1x3 1x4 1x5 2x3 2x4 2x5 3x4 3x5 4x5 Total
2x2 4 4
3x3 12 6 4 22
4x4 24 16 8 12 6 4 70
5x5 40 30 20 10 24 16 8 12 6 4 170

NOTICE ANYTHING???

1--The number of 1 square wide rectangles in each case is equal to n^2(n-1).
2--The number of 2 square wide rectangles in each case is equal to the number of 1 square wide rectangles in the previous case. The number of 3 square wide rectangles in each case is equal to the number of 2 square wide rectangles in the previous case.

The total number of rectangles in a square of nxn squares is equal to the sum of the 1 square wide rectangles for each rectangle from the 2x2 up to and including the nxn one being considered. Thus, the number of rectangles in a 5x5 square is the sum of the 1 square wide rectangles in the 1x1, 2x2, 3x3, 4x4, and 5x5 squares or 4 + 18 + 48 + 100 = 170. Therefore, for the typical chess board problem of 8x8 squares, we have a total of 4 + 18 + 48 + 100 + 180 + 294 + 448 = 1092.


A general expression for the number of pure rectangles can be derived from the following extension of our data so far.
Term.........1........2........3.........4.........5........6.........7.........................n = number of cells per side
Squares...1x1....2x2.....3x3.....4x4.....5x5.....6x6.....7x7.....8x8
R..............0........4........22......70......170.....350.....644....1092.............N = number of internal rectangles
1st diff...........4........18......48......100.....180.....294.....448
2nd diff..............14.......30......52........80.....114....154
3rd diff....................16.......22.......28.......34......40
4th diff..........................6.........6.........6........6

We again have a finite difference series ending in the constant difference of 6. Again, an expression can be derived enabling the definition the nth term of any finite difference series. The expression is a function of the number of successive differences required to reach the constant difference. If the first differences are constant, the expression is of the first order, i.e., N = an + b. If the second differences are constant, the expression is of the second order, i.e., N = an^2 + bn + c. Similarly, constant third differences derive from N = an^3 + bn^2 + cn + d. Our case will derive from N = an^4 + bn^3 + cn^2 + dn + e.

Using the data points (n1, N1), (n2,N2), (n3,N3), etc., we substitute them into N = an^4 + bn^3 + cn^2 + dn + e as follows:
(n1,N1) = (1,0) produces a(1^4) + b(1^3) + c(1^2) + d(1) + e = 0 or a + b + c + d + e = 0.
(n2,N2) = (2,4) produces a(2^4) + b(2^3) + c(2^2) + d(2) + e = 4 or 16a + 8b + 4c + 2d + e = 4.
(n3,N3) = (3,22) produces a(3^4) + b(3^3) + c(3^2) + d(3) + e = 22 or 81a + 27b + 9c + 3d + e = 22.
(n4,N4) = (4,70) produces a(4^4) + b(4^3) + c(4^2) + d(4) + e = 70 or 256a + 64b + 16c + 4d + e = 70.
(n5,N5) = (5,170) produces a(5^4) + b(5^3) + c(5^2) + d(5) + e = 170 or 625a + 125b + 25c + 5d + e = 170.

The solution to these four expressions leaves us with the number of individual rectangles within a square divided up into nxn smaller squares being N = [ 3n^4 + 2n^3 - 3n^2 - 2n]
12

Letting N(s,r)n = the total number of squares and rectangles in a square of nxn squares, we can also use

N(s,r)n = n(n + 1)(2n + 1)/6 + n(3n^3 + 2n^2 - 3n - 2)/12 = [(n^2 + n)^2]/4

For our 8x8 board, N(s,r)8 = [(n^2 + n)^2]/4 = [(64 + 8)^2]/4 = 1296

It is worth noting that [(n^2 + n)^2/4 = [n(n + 1)/2]^2 where n(n + 1)/2 is the nth triangular number. Thus, the number of squares and rectangles within a square of nxn cells derives from the square of the nth triangular number.

nxn squares...............1.....2.....3.....4......5.....6......7.......8
Tn.............................1.....2.....6....10....15....21....28.....36
Squares + Rect..........1.....4....36..100..225..441...784..1296

We can also derive this same expression by simply adding together the number of square and rectangles within a given square as N(s,r) = (2n^3 + 3n^2 + n)/6 + (3n^4 + 2n^3 - 3n^2 - 2n)/12 = (n^4 + 2n^3 + n^2)/4.


Lets now generalize the problem even further by considering a rectangle to start with. Lets first determine the number of squares within a rectangle, the rectangle dimensions obviously being a multiple of some square. We will start with a rectangle of n by (n + 1) squares. In the usual manor of counting squares, we get the following data:

..n.............1.....2......3.....4......5.....6......7
Rect........1x2..2x3..3x4..4x5..5x6..6x7..7x8
Cells.........2.....6.....12....20....30....42...56
Squares....2.....8.....20....40....70...112
1st Diff.........6.....12....20....30....42
2nd Diff...........6.......8.....10....12
3rd Diff................2......2......2

We now have a finite difference series ending in the constant difference of 2. Again, an expression can be derived enabling the definition the nth term of any finite difference series. The expression is a function of the number of successive differences required to reach the constant difference. If the first differences are constant, the expression is of the first order, i.e., N = an + b. If the second differences are constant, the expression is of the second order, i.e., N = an^2 + bn + c. Similarly, constant third differences derive from N = an^3 + bn^2 + cn + d. Our case will derive from N = an^4 + bn^3 + cn^2 + dn + e.

Using the data points (n1, N1), (n2,N2), (n3,N3), etc., we substitute them into N = an^3 + bn^2 + cn + d as follows:

For (n1,N1) = (1,1) we get a(1^3) + b(2^2) + c(1^1) + d = a + b + c + d = 2
For (n2,N2) = (2,5) we get a(2^3) + b(2^2) + c(2^1) + d = 8a + 4b + 2c + d = 8
For (n3,N3) = (3,14) we get a(3^3) + b(3^2) + c(3^1) + d = 27a + 9b + 3c + d = 20
For (n4,N4) = (4,30) we get a(4^3) + b(4^2) + c(4^1) + d = 64a + 16b + 4c + d = 40

The solution of these four expressions leads us to a = 1/3, b = 1, c = 2/3, and d = 0 resulting in our general expression of N = [2n^3 + 6n^2 + 4n]/6.

Lets now explore a rectangle of n by (n + 2) squares. In the usual manor of counting squares, we get the following data:

..n.............1.....2......3.....4......5.....6......7
Rect........1x3..2x4..3x5..4x6..5x7..6x8..7x9
Cells.........3.....8.....15....24....35....48...63
Squares....3....11.....26....50....85...133
1st Diff.........8.....15....24....35....48
2nd Diff...........7.......9.....11....13
3rd Diff................2......2......2

Following the same procedure as used earlier, we end up with a = 1/3, b = 3/2, c = 7/6, and d = 0 resulting in our general expression of N = [2n^3 + 9n^2 + 7n]/6.

By comparing the three expressions now derived for the number of squares in a square and rectangles, we can define the more general expression of N = [2n^3 + 3(3p + 3)n^2 + (3p + 1)n]/6 where p = the additional number of squares along one edge of the rectangle. In other words, p = 1 defines an n by (n + 1) rectangle, p = 2 defines an n by (n + 2) rectangle, and so on, n being the number of squares along one side of the rectangle.


By no strange coincidence, what we have already derived applies to determining the total number of rectangles within a random size rectangle. If we simply visualize the n by n square and move all the lines in such a way as to create all rectangles within, the total number of rectangles will be the same as the total number of squares and rectangles we discovered in the pure square or N = (n^4 + 2n^3 + n^2)/4 = Tn^2.


There is another way of deriving the second expression for the total number of rectangles within a rectangle. A picture will help to visualize the reasoning. If you draw the lines such that none of the smaller figures within the outer boundry of the rectangle is a pure square, then the problem is simpler. I suggest we try 3 vertical and 3 horizontal lines first and see what you get and how you got it.

.1.......2.......................3
A____F_____________B....1
I I I
I I I
I I I
I____I______________IG..2
IJ IE I
I I I
I____I______________I
D H C...3

You should have 9 rectangles if your boxes are all rectangular, ABCD, ABGJ, CDJG, AFHD, BCHF, AFJE, BGEF, CHEG, and DJEH.

Assume we have a rectangle divided up into n vertical columns and n horizontal rows. Each rectangle we must count is made up of two vertical lines and two horizontal lines. There are n + 1 lines to choose from for each rectangle. Now, any two lines may be selected from (n + 1) lines in n(n + 1)/2 ways. The quantity n(n + 1)/2 happens to be the general expression for a triangular number, Tn (the sequential sum of rows of dots in the shape of an equilateral triangle). Since the selections are the same for vertical and horizontal lines, the total number of selection choices becomes (Tn)^2, n being the number of columns and rows forming the sides of the rectangles. Checking our 8x8 chess board squares problem, assuming that the lines do not form squares but randomly sized rectangles, the total number of rectangles is then derived from N(8x8) = [8(9)/2]^2 = 36^2 = 1296.

We have now reached our ultimate scenario. What about the number of rectangles in a given rectangle where the number of rows and columns are different, say m columns and n rows?

We then end up with N(mxn) = [m(m + 1)/2]x[n(n + 1)/2] = mn(m + 1)(n + 1)/4.

 

[soroban]

Hello, jbsdad!

I am trying to determine what is the maxium number of squares determined by a 7 x 7 figure.
What is the formula/solution?

Sketch a 7-by-7 chessboard. .
Then we can count the number of various-sized squares.

Obviously, there is 1 7-by-7 square.

Place a 6-by-6 square in the upper-left corner.
. . It can be moved one space to the right, or one space down,
. . or both one space right and one space down.
There are: .2[sup:3tjgyeuc]2[/sup:3tjgyeuc] 6-by-6 squares.

Place a 5-by-5 square in the upper-left corner.
.It can be moved one or two spaces to the right
. . and/or one or two spaces down.
There are: .3[sup:3tjgyeuc]2[/sup:3tjgyeuc] 5-=by-5 squares.

. . Do you see the pattern?

There are: .4[sup:3tjgyeuc]2[/sup:3tjgyeuc] 4-by-4-squares.
There are: .5[sup:3tjgyeuc]2[/sup:3tjgyeuc] 3-by-3 squares.
There are: .6[sup:3tjgyeuc]2[/sup:3tjgyeuc] 2-by-2 squares.
There are: .7[sup:3tjgyeuc]2[/sup:3tjgyeuc] 1-by-1 squares.

The number of squares is: .\(\displaystyle 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 \:=\:140\)
. . That is the solution.


If you want a formula for this problem, TchrWill has derived it for you.

. . \(\displaystyle \text{Sum of the first }n\text{ squares: }\;S_n \;=\;\frac{n(n+1)(2n+1)}{6}\)