10th Chinese 1995 Problem A3 What real values of x and y minimise ∑ |a(x + y - 10b)(3x - 6y - 36c)(19x + 95y - 95a)|, where the sum is taken over all triples a, b, c with 0 < a, b, c ≤ 10, and what is the minimum value?
250·900·112·95 = 2394 million, achieved, for example, by x = 55, y = -4. Solution |x - k| + |x - 2k| + ... + |x - nk| is a piecewise linear function of x and if n is even, its middle segment is horizontal. Thus for n = 10, we minimise the function with any value of x in the closed interval [5k, 6k]. The minimum value is k + 2k + 3k + 4k + 5k + 4k + 3k + 2k + k = 25k. So, viewed as a function of (x + y), ∑ b |x + y - 10b| has minimum value 250 for any (x + y) in the range [50, 60]. Similarly, ∑ c |3x - 6y - 36c| has minimum value 25·36 = 900 for any (3x - 6y) in the range [180, 216] or (x - 2y) in the range [60, 72]. The sum ∑|a(19x + 95y - 95a)| is also a piecewise linear function of (19x + 95y). The slope of the segments increases as we move to the right. The segment just to the left of 19x + 95y = 7·95 is 1+2+3+4+5+6-7-8-9-10 = -13, and the segment just to the right of 19x + 95y = 7·95 is 1+2+3+4+5+6+7-8-9-10 = 1. So the minimum value is only achieved for 19x + 95y = 7·95, or x + 5y = 35 and is (1·6 + 2·5 + 3·4 + 4·3 + 5·2 + 6·1 + 8·1 + 9·2 + 10·3) 95 = 112·95. Clearly if we can find x, y which minimise each of these three sums separately, then we also minimise their product. So we find out first whether that is possible. We need x + 5y = 35. Then x + y in [50, 60] implies that y lies in [-6¼, -3¾] and hence x in [53¾, 66¼]. Similarly, x - 2y in the range [60, 72] implies y in the range [-5 2/7, -3 4/7 ] and hence x in the range [52 6/7, 61 3/7]. These ranges overlap, so we can choose x, y to minimise each of the three sums. For example, we can take y = -4, x = 55. Hence the minimum value of the product is 250·900·112·95. 10th Chinese 1995 © John Scholes jscholes@kalva.demon.co.uk 5 Jan 2003 Last corrected/updated 5 Jan 03