Maths Olympiad Prep

Library / /125 of 462

Combinatorics Difficulty 5.3 AIME, harder Prove it Ireland

Find all pairs of positive integers (a,b)(a, b) for which
(a+12)(b+12)=630. \binom{a+1}{2} \binom{b+1}{2} = 630.

Solution

Let f(a)=(a+12)f(a) = \left(\frac{a+1}{2}\right), then f(1)=1f(1) = 1 and f(35)=630f(35) = 630. Because f(a)>630f(a) > 630 for a>35a > 35, any solution (a,b)(a, b) satisfies 1a,b351 \le a, b \le 35 and f(a)f(a) and f(b)f(b) are divisors of 630=23257630 = 2 \cdot 3^2 \cdot 5 \cdot 7. If aa is odd, aa is a factor of f(a)f(a). If aa is even, a+1a+1 is odd and a factor of f(a)f(a). The odd positive divisors of 360 not exceeding 36 are 1, 3, 5, 7, 9, 15, 21 and 35. If aa is among these numbers and f(a)f(a) is a factor of 630, (a+1)/2(a+1)/2 is a factor of 630 as well. This is the case for the numbers 1, 2, 5, 9, 35. If x=a+1x = a + 1 is among these numbers and f(a)f(a) is a factor of 630, a/2=(x1)/2a/2 = (x-1)/2 will be a factor of 630. This is the case for aa being one of 2, 4, 6, 14, 20. The values f(a)f(a) for these numbers are collected in the following table.

a1234569142035
(a+1)/2(a+1)/213610152145105210630

Because none of the quotients 630/10=63630/10 = 63, 630/15=42630/15 = 42, 630/21=30630/21 = 30 and 630/45=14630/45 = 14 occur in this table, no solution can have aa or bb equal to 4, 5, 6 or 9. The other values for aa lead to the following complete list of solutions:
(a,b)=(3,14),(14,3),(2,20),(20,2),(1,35),(35,1). (a, b) = (3, 14), (14, 3), (2, 20), (20, 2), (1, 35), (35, 1).

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.