Maths Olympiad Prep

Library / /12 of 15

Combinatorics Difficulty 5.9 AIME, harder Prove it Estonia

Find all pairs (m,n)(m, n) of positive integers for which the m×nm \times n grid contains exactly 225225 rectangles whose side lengths are odd and whose edges lie on the lines of the grid.

Solution

The m×nm \times n grid is formed by m+1m+1 horizontal and n+1n+1 vertical lines. Number the horizontal lines with numbers from 11 to m+1m+1 and the vertical lines with numbers from 11 to n+1n+1. Rectangles with odd side lengths arise if and only if two horizontal lines with different parity and two vertical lines with different parity intersect.

Assume that at least one of the numbers mm and nn is even. We can assume without loss of generality that m=2km = 2k. Then there are exactly k+1k+1 odd-numbered and kk even-numbered horizontal lines and thus there are k(k+1)k(k+1) pairs of lines of different parity. But this means that overall the number of rectangles with odd side lengths is even and cannot be 225225. Therefore mm and nn are both odd numbers.

Let now m=2k1m = 2k-1 and n=2l1n = 2l-1. Then we have exactly kk even-numbered and kk odd-numbered horizontal lines and ll even-numbered and ll odd-numbered vertical lines. Overall it is possible to form kkll=(kl)2k \cdot k \cdot l \cdot l = (kl)^2 rectangles with odd side lengths. From (kl)2=225(kl)^2 = 225 we get kl=15kl = 15. The solutions are k=1,l=15k=1, l=15 or k=3,l=5k=3, l=5 (or vice versa). So m=1,n=29m=1, n=29 or m=5,n=9m=5, n=9 (or vice versa).

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.