Library / /1 of 69

, 2011

Combinatorics Difficulty 3.8 AMC 10/12 Find the answer South Africa

A little boy Mak has drawn a rectangle of size $20 \times 15$ , and divided it by straight lines into unit squares. How many squares (of any size) are there in Mak's picture?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Consider a square of side length $d$ , and the position of its bottom-right unit square. It has $d-1$ squares above, and $d-1$ squares to the left of it. Hence there are $(21-d)(16-d)$ possibilities for the bottom-right corner, resulting in $(21-d)(16-d)$ squares of size $d$ appearing in the grid. The total number of squares is
$\begin{aligned} S &= \sum_{d=1}^{15} (21 - d)(16 - d) \\ &= \sum_{d=1}^{15} (336 - 37d + d^2) \\ &= 15 \cdot 336 - 37 \sum_{d=1}^{15} d + \sum_{d=1}^{15} d^2 \\ &= 15 \cdot 336 - 37 \frac{15 \cdot 16}{2} + \frac{15 \cdot 16 \cdot 31}{6} \\ &= 1840. \end{aligned}$

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.