Maths Olympiad Prep

Library / /9 of 120

, 2012

Combinatorics Difficulty 4.6 AIME Prove it Saudi Arabia

Divide a rectangle of dimension m×nm \times n by lines parallel to the sides into mnmn congruent squares. Find the number of squares in this configuration.

Solution

There are mnmn squares of length side 11, (m1)(n1)(m-1)(n-1) squares of length side 22, (m2)(n2)(m-2)(n-2) squares of side length 33, etc.
Assume that mnm \ge n. The total number of squares in this configuration is
k=0n1(mk)(nk).(1) \sum_{k=0}^{n-1} (m-k)(n-k). \quad (1)
We have
k=0n1(mk)(nk)=k=0n1(mn(m+n)k+k2)=mn2(m+n)(n1)n2+(n1)n(2n1)6=mn2m(n1)n2(n1)n22+(n1)n(2n1)6=n(n+1)(3mn+1)6. \begin{aligned} \sum_{k=0}^{n-1} (m-k)(n-k) &= \sum_{k=0}^{n-1} (mn - (m+n)k + k^2) \\ &= mn^2 - (m+n) \frac{(n-1)n}{2} + \frac{(n-1)n(2n-1)}{6} \\ &= mn^2 - m \frac{(n-1)n}{2} - \frac{(n-1)n^2}{2} + \frac{(n-1)n(2n-1)}{6} \\ &= \frac{n(n+1)(3m-n+1)}{6}. \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 and solution reproduced as published; topic and difficulty added by this site.