Finding Squares – 1
Drawn in red in this grid are two 1 by 1 squares and one 2 by 2 square with horizontal and vertical sides.
THE CHALLENGE
Find the number of squares of all sizes with horizontal and vertical sides in this grid.
EXPLORATION
Play with even bigger grids. Can you discover a systematic way to count all the squares? How does your answer change, if at all, if the grid of points is a rectangle that is not a square?
Notes
THE CHALLENGE
The possible squares have side lengths from 1 up to 4.
For each size of square, think of the upper left corner as the starting position. You can produce all squares of this size in the grid by shifting this starter square around. You have the choice of moving it to the right or down the remaining number of positions. These are independent choices, so you get <this number plus 1> squared of that size square.
For example, suppose you are counting 1 by 1 squares in this 4 by 4 grid. A 1 by 1 square in the upper left-hand corner can be shifted 1 or 2 to the right and 1 or 2 down. So there are 3 possible positions horizontally (counting the original position) and 3 possible positions vertically. Thus there are 3 x 3 of these 1 by 1 squares.
For the original 4 by 4 grid problem, this gives the following count:
- 1 by 1 squares: 3 x 3 = 9
- 2 by 2 squares: 2 x 2 = 4
- 3 by 3 squares: 1 x 1 = 1.
There are a total of 3 x 3 + 2 x 2 + 1 x 1 = 9 + 4 + 1 = 14 possible squares.
EXPLORATION
For any square grid, the total number of squares will be the sum of the square numbers less than the size of the grid. For example, a 7 by 7 grid will have 36 + 25 + 16 + 9 + 4 + 1 = 91 squares.
Rectangular grids are almost as easy to count. The smaller of the two dimensions of the rectangle will restrict the maximum size of the possible squares. Count them in a similar way as the square grid case. Rather than doing the general case, let’s just do one illustrative example.
Suppose you are counting the squares in a 5 by 7 grid. Because there are only 5 rows, no square can be bigger than 4 by 4.
- 1 by 1 squares: 4 x 6 = 24
- 2 by 2 squares: 3 x 5 = 15
- 3 by 3 squares: 2 x 4 = 8
- 4 by 4 squares: 1 x 3 = 3
The total number of squares is 24 + 15 + 8 + 3 = 50.