Maths Olympiad Prep

Library / /65 of 68

, 2017

Number theory Difficulty 6.9 National Olympiad Prove it United States

Problem:

Consider all ordered pairs of integers (a,b)(a, b) such that 1ab1001 \leq a \leq b \leq 100 and
(a+b)(a+b+1)ab \frac{(a+b)(a+b+1)}{a b}
is an integer.
Among these pairs, find the one with largest value of bb. If multiple pairs have this maximal value of bb, choose the one with largest aa. For example choose (3,85)(3,85) over (2,85)(2,85) over (4,84)(4,84). Note that your answer should be an ordered pair.

Solution

Solution:

Firstly note that (a+b)(a+b+1)ab=2+a2+b2+a+bab\frac{(a+b)(a+b+1)}{a b}=2+\frac{a^{2}+b^{2}+a+b}{a b}. Let cc be this fraction so that (a+b)(a+b+1)=ab(c+2)(a+b)(a+b+1)=a b(c+2) for some integers a,b,ca, b, c. Suppose (a,b)(a, b) with aba \geq b is a solution for some cc. Consider the quadratic
x2(bc1)x+b2+b=0 x^{2}-(b c-1) x+b^{2}+b=0
It has one root aa, and the other root is therefore bca1b c-a-1. Furthermore the other root can also be expressed as b2+bab2+bb+1=b\frac{b^{2}+b}{a} \leq \frac{b^{2}+b}{b+1}=b, so that 0<bca1b0<b c-a-1 \leq b. In particular, (b,bca1)(b, b c-a-1) is a solution as well.
Thus all solutions (a,b)(a, b) reduce to a solution where a=ba=b, at which point c=2+2ac=2+\frac{2}{a}. Since a,ca, c are positive integers we thus have a=1,2a=1,2, and so c=3,4c=3,4.
Through this jumping process, we iteratively find the solutions for c=3c=3 :
(2,2)(2,3)(3,6)(6,14)(14,35)(35,90) (2,2) \rightarrow(2,3) \rightarrow(3,6) \rightarrow(6,14) \rightarrow(14,35) \rightarrow(35,90)
and c=4c=4 :
(1,2)(2,6)(6,21)(21,77) (1,2) \rightarrow(2,6) \rightarrow(6,21) \rightarrow(21,77)
so that the desired pair is (35,90)(35,90).

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.