When to be sure that we have counted all the squares in such problems

1.6k Views Asked by At

My first question is: How would one solve such problems (in general,squares+rectangles). What should be the general technique?How can this problem be reduced to a mathematical problem?

enter image description here

My second question is: When to be sure that we have counted all the squares in such problems?

1

There are 1 best solutions below

2
On

A general procedure:

  • identify all line segments, taking them as long as possible. In the figure, there are 18 of them (10 forming the main grid, 8 forming the extra squares);

  • when a line segment has parts, consider all their decompositions, which count as a triangular number (a main grid line can be decomposed in 1 + 2 + 3 + 4 ways and a side of an extra square in 1 + 2 ways, in total, 10 x 10 + 8 x 3 = 124 chunks);

  • for every part of every segment, check if it is the side of a square; there are two possibilities each time.

  • finally take the total count and divide it by four (as you have counted every square four times).

A specific procedure:

A full grid of N² equal squares contributes $\frac{N(N+1)(2N+1)}6$ squares (pyramidal number).

In the given case, a 5x5 grid and two 2x2 grids for a total of $40$.