suares with lines

Question

how many squares with horizontal and vertical sides can be formed using points of the grid as vertices?

 

 

Also, the dots are 4 down and to the right. In  total is 16 dots.

Answer 1

Hi Annie

I'm assuming your grid looks something along the lines of this below

 

 _ _  _ 

|_|_|_|

|_|_|_|

|_|_|_|

 

There are many ways to solve this problem, here's one example

 

Start with the smallest possible square size, 1x1

number 1x1 = 3x3 = 9

 

The next possible size is 2x2

number 2x2 = 2x2 = 4

 

The next possible size is 3x3
number 3x3 = 1x1 = 1

 

The sum is 14

 

If you increase the size of your grid

 _ _  _ _
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|

|_|_|_|_|

 

square size, 1x1
number 1x1 = 4x4 = 16

The next possible size is 2x2
number 2x2 = 3x3 = 9

The next possible size is 3x3
number 3x3 = 2x2 = 4

 

The next possible size is 4x4
number 4x4 = 1x1 = 1

The sum is 30

 

You can use this to find the number of possible squares for any grid size, Number of squares = sum((k-1)x(k-1)), k=2->n, n is the number of horizontal dots in your grid

Answer 2

In general, let S_n be the number of squares (n  ≥ 1) of a grid with n points on a side.

 

Then S_n = n * (n -1) * (2n - 1)/6

 

Note S₄ = 4*3*7/6 = 14

        S₅ =5*4*9/6  = 30

 

Proof by Mathematical Induction

 

Let n = 1.  With only one point there are no squares.

 

S₁ = 1* 0 * 1/6 = 0, so the formula works with 1 point.

 

Assume the formula is true for n = k points and consider (k + 1) points.

 

    _ _ _ _B
A |_|_|_|_|  This is a rough representation of
   |_|_|_|_|  what is being done.
   |_|_|_|_|
   |_|_|_|_|

 

Start with the grid of size k x k

When another point is added, then the new row A and

new column B are created.

The new grid is now (k+1) x (k+1)

 

Any new rectangles would be obtained from the new row A

and row B. Let m be the number of new rectangles.

The size of the new rectangles is from size 1 to k.

 

∴ S_k+1 = S_k + m

 

The sizes of the new rectangles are  from size 1 to k.

 

The number of new rectangles of size 1 is k from row A and (k-1) from column B.

This is one less than from row A because the top right rectangle has already

been counted as part of the count in row A.

The number of new size 1 rectangles is 2*k-1

 

The number of new rectangles of size 2, starting from the second column, is (k-1)

and from column B is (k-2).  Again the top right rectangle has been included only

once.

The number of new size 2 rectangles is 2*k-3

 

Continuing this process:

  The number of size 3 is 2*k-5

  The number of size 4 is 2*k-7

  .

  .

  .

  The number of size k-1 is 3

  The number of size k is 1

 

Then the number of new rectangles m = (2k-1) + (2k-3) + .. + 3 + 1

 

                                                             = ∑(2i - 1) [i from 1 to k]

 

                                                             = 2∑i - k

 

                                                             = 2 *k(k+1)/2 - k

 

                                                             = k² +k - k = k²

 

From, S_k+1 = S_k + m and S_k= k * (k -1) * (2k - 1)/6

 

∴ S_k+1 = k * (k -1) * (2k - 1)/6 + k²

 

            = (k/6)(2k² - 3k + 1 + 6k)

 

           = (k/6)(2k² + 3k + 1)

 

           = (k/6)(2k+1)(k+1)

 

          = (k+1)([k+1]-1)(2[k+1]-1)/6

 

Since the result for S_k+1 is the same as S_n evaluated with n=k+1, the result is

true by mathematical induction.

 

 

Answer 3

The following answer is for an array of 5 by 5 dots:

 

There are 16 1×1 squares.

Starting in the lefthand upper corner, you can form 9 2×2 squares;

Starting in the lefthand upper corner, you can form 4 3×3 squares;

Starting in the lefthand upper corner, you can form 1 4×4 square.

 

Answer: 16 + 9 +  4 + 1 = 30.  Very interesting pattern.

 

So I reckon that with 4 by 4 dots, there would be only the last three terms (9 + 4 + 1) = 14.

 

Answer revised