Maths Olympiad Prep

Library / Irish Mathematical Olympiad /68 of 236

Irish Mathematical Olympiad

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 1≤a,b≤351 \le a, b \le 35 and f(a)f(a) and f(b)f(b) are divisors of 630=2⋅32⋅5⋅7630 = 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=(x−1)/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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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