IMO 1989 SL 31

Origin: SWE

Problem

Let a1 \geqa2 \geqa3 be given positive integers and let N(a1, a2, a3) be the number of solutions (x1, x2, x3) of the equation a1 x1

• a2 x2
• a3 x3 = 1, where x1, x2, and x3 are positive integers. Show that N(a1, a2, a3) \leq6a1a2(3 + ln(2a1)).

Solution

Let us denote by Npqr the number of solutions for which ap/xp \geqaq/xq \geq ar/xr, where (p, q, r) is one of six permutations of (1, 2, 3). It is clearly enough to prove that Npqr + Nqpr \leq2a1a2(3 + ln(2a1)). First, from 3ap xp \geqap xp

• aq xq
• ar xr = 1 and ap xp < 1 we get ap + 1 \leqxp \leq3ap. Similarly, for fixed xp we have 2aq xq \geqaq xq
• ar xr = 1 −ap xp and aq xq \leqmin ap xp , 1 −ap xp  ,

which gives max {aq \cdot xp/ap, aq \cdot xp/(xp −ap)} \leqxq \leq2aq \cdot xp/(xp −ap), i.e., if ap +1 \leqxp \leq2ap there are at most aq \cdot xp/(xp −ap)+1/2 possible values for xq (because there are [2x] −[x] = [x + 1/2] integers between x and 2x), and if 2ap+1 \leqxp \leq3ap, at most 2aq \cdot xp/(xp −ap)−aq \cdot xp/ap+ 1 possible values. Given xp and xq, xr is uniquely determined. Hence Npqr \leq 2ap  xp=ap+1  aq \cdot xp xp −ap

• 1 

3ap  xp=2ap+1 2aq \cdot xp xp −ap −aq \cdot xp ap

• 1  = 3ap
• aq ap  k=1 k + ap k

2(k + 2ap) k + ap −k + 2ap ap  = 3ap

• aq ap  k=1

1 −k ap

• ap  1 k + k + ap  = 3ap −aq 2 + apaq

2 + ap  k=1 1 k + k + ap  \leqapaq  3 2aq − 2ap

• ln(2ap) + 5 2 −ln 2  , where we have used n k=1 (1/k + 2/(k + n)) \leqln(2n) + 2 −ln 2 (this can be proved by induction). Hence, Npqr + Nqpr \leq2apaq(1 + 0.5 + ln(2ap) + 2 −ln2) < 2a1a2(2.81 + ln(2a1)). Remark. The official solution was somewhat simpler, but used that the interval (x, 2x], for real x, cannot contain more than x integers, which is false in general. Thus it could give only a weaker estimate N \leq6a1a2 (9/2 −ln 2 + ln(2a1)).