Maths Olympiad Prep

Library / /6 of 11

Algebra Difficulty 6.0 National Olympiad Prove it Singapore

Let a,b,c,da, b, c, d be positive integers such that a+c=20a + c = 20 and ab+cd<1\frac{a}{b} + \frac{c}{d} < 1. Find the maximum possible value of ab+cd\frac{a}{b} + \frac{c}{d}.

Solution

Therefore the maximum value of the sum of the fractions is attained when yy is minimum, which is 11. When y=1y = 1, since ac<xyac < xy, the optimum value for xx is ac+1ac + 1 (we want to choose xx so that it is as small as possible). Thus for fixed a,ca, c, the maximum value is
aa+ac+1+cc+1=11(a+ac+1)(c+1). \frac{a}{a+ac+1} + \frac{c}{c+1} = 1 - \frac{1}{(a+ac+1)(c+1)}.
By checking all pairs (a,c)=(1,19),(2,18),,(10,10)(a, c) = (1, 19), (2, 18), \dots, (10, 10), we find that the maximum value of (a+ac+1)(c+1)(a + ac + 1)(c + 1) is 13861386, attained when (a,c)=(7,13)(a, c) = (7, 13). Therefore the maximum value is 111386=138513861 - \frac{1}{1386} = \frac{1385}{1386}.

We shall use the following result. Let p,q,kp, q, k be positive integers. Then pp+k<qq+k\frac{p}{p+k} < \frac{q}{q+k} iff p<qp < q.

First fix a,ca, c. Without loss of generality, we assume that aca \le c. Let b=a+xb = a + x and d=c+yd = c + y where x,yx, y are positive integers. Then it is easy to see that
aa+x+cc+yaa+y+cc+x \frac{a}{a+x} + \frac{c}{c+y} \ge \frac{a}{a+y} + \frac{c}{c+x}
if yxy \le x. Thus we may assume that yxy \le x. Also
1>ab+cd=aa+x+cc+y=ac+ay+ac+cxac+ay+xy+cx 1 > \frac{a}{b} + \frac{c}{d} = \frac{a}{a+x} + \frac{c}{c+y} = \frac{ac + ay + ac + cx}{ac + ay + xy + cx}
Thus ac<xyac < xy and xyacxy - ac is the difference of the denominator and numerator of the fraction on the RHS. Thus if x,yx', y' are positive integers such that yxy' \le x' and xy=xyxy = x'y', then yyxx|y - y'| \le |x - x'|. Therefore

aa+x+cc+yaa+x+cc+y(a+x)(c+y)(a+x)(c+y)a(yy)c(xx)yyandxx\begin{align*} \frac{a}{a+x} + \frac{c}{c+y} &\le \frac{a}{a+x'} + \frac{c}{c+y'} \\ \Leftrightarrow (a+x)(c+y) &\le (a+x')(c+y') \\ \Leftrightarrow a(y - y') &\le c(x' - x) \\ \Leftrightarrow y &\ge y \quad \text{and} \quad x' \ge x \end{align*}

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.