Maths Olympiad Prep

Library / February /59 of 62

February, 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 1≤a≤b≤1001 \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 a≥ba \geq b is a solution for some cc. Consider the quadratic
x2−(bc−1)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 bc−a−1b c-a-1. Furthermore the other root can also be expressed as b2+ba≤b2+bb+1=b\frac{b^{2}+b}{a} \leq \frac{b^{2}+b}{b+1}=b, so that 0<bc−a−1≤b0<b c-a-1 \leq b. In particular, (b,bc−a−1)(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,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.