Problem 416

We can systematically count the number of squares by considering
the possible sizes of the squares.

Case 1: Squares of size $1\times1$.

There are 34 such squares.

Case 2: Squares of size $2\times2$.

Begin with a $2\times2$ square in
the top left corner of the diagram. Shifting this $2\times2$ square one column to the right
gives a second $2\times2$ square.
Shifting this second $2\times2$
square one column to the right again gives a third $2\times2$ square. Thus, there are $3$ such $2\times2$ squares within the top two rows
of the diagram.

Each of these $3$ squares can be
shifted down one row to give $3$ more
$2\times2$ squares, each contained
within the second and third rows of the diagram. Continuing in this way,
there are $3$ such $2\times2$ squares within rows three and
four, rows four and five, rows five and six, and rows six and seven.
Thus, there are $3\times6=18$ such
$2\times2$ squares.

The first and the last of these $18$
squares are shown in the following diagram.

[[IMAGE0]]

There are $4$ additional $2\times2$ squares. One of these occupies
the leftmost two squares within rows five and six. This square can be
shifted down one row, and each of these $2\times2$ squares can be shifted four
columns to the right. The first and the last of these 4 squares are
shown in the following diagram.

[[IMAGE1]]

In total, there are $18+4=22$
squares of size $2\times2$.

Case 3: Squares of size $3\times3$.

Beginning with a $3\times3$ square
in the top left corner of the diagram and counting in a similar way,
there are $2$ such $3\times3$ squares within the top three
rows of the diagram.

There are $2$ such $3\times3$ squares within rows two through
four, rows three through five, rows four through six, and finally rows
five through seven. Thus, there are $2\times5=10$ such $3\times3$ squares. The first and the last
of these $10$ squares are shown in
the following diagram.

[[IMAGE2]]

There are $2$ additional $3\times3$ squares. One of these occupies
the leftmost three squares within rows five through seven. The second of
these occupies the rightmost three squares within rows five through
seven.

These $2$ squares are shown in the
following diagram.

[[IMAGE3]]

In total, there are $10+2=12$
squares of size $3\times3$.

Case 4: Squares of size $4\times4$.

There is a $4\times4$ square that
occupies all four columns within rows one through four. This square can
be shifted downward one row to occupy rows two through five, shifted
downward one row again to occupy rows three through six, and finally one
more time to occupy rows four through seven. These are the only $4\times4$ squares and thus there are $4$ in total. The first and the last of
these $4$ squares are shown in the
following diagram.

[[IMAGE4]]

There are no squares with dimensions greater than $4\times4$, and so there are $34+22+12+4=72$ squares of all sizes in the
diagram.