16th Chinese 2001 Problem B3 Let S be the set of all ordered pairs of positive integers (m, n) such that: (1) m < 4002; (2) 2n divides (4002m - m 2 + n 2 ); and (3) n 2 - m 2 + 2mn <= 4002(n - m). Find the maximum and minimum values for (4002m - m 2 - mn)/n for (m, n) in S. Solution
: 3750 (m = 50, n = 52 or m = 75, n =77), 2 (m = 2, n = 2000). From (2), 2 must divide m 2 - n 2 , so m and n must have the same parity. We show next that n > m and m + n  4002, then (*) implies 2mn  n - (4002-m) (since 4002-m > 0 by (1) ), and m > m - n. So we must have m + n  m. From (2) n divides 4002m - m 2 . Suppose 4002m - m 2 = nk. Since 4002 > m + n, we have 4002m > m 2 + mn and hence 4002m - m 2 > nm. Hence k > m. Put f(m, n) = (4002m - m 2 - mn)/n = (4002 - n - m) m/n. Then f(m, n) = k - m. So f(m, n) must be a positive integer. (2) gives that 2n divides n(n + k), so n+ k must be even. Hence m, n, k are all the same parity. Hence f(m, n) must be even and hence at least 2. But f(2, 2000) = 2, so that is the minimum value. Now consider the maximum of f(n, m). Since m and n have the same parity and n > m, we have m/n  0). The range in x corresponds to a range in m of 50, 51, ... , 75. But if n = m+2, then from (2), m+2 must divide 4002m - m 2 and hence 4002m - m 2 + m(m+2) = 4004m = 4·7·11·13 m. So if m is odd, then m+2 must divide 7·11·13. The only possible m (in the range 50 to 75) is 75. Similarly, if m is even, then 2(m+2) must divide 4·7·11·13 m, and the only possible candidates are m is 50 and 54. It is easy to check that m = 50 and m = 75 work and give the value 3750. But m = 54 does not work. Can we do better by taking n - m > 2? Suppose n = m+4, then f(m, n) = (4002 - x)(x/2 - 2)/(x/2 + 2). But it is easy to show that (4002 - x)(x/2 - 2)  0). Obviously if n - m is larger we do even worse. Many thanks to Tang Lek Huo for pointing out the error in my original statement of the problem. He also provided a similar solution to that above. 16th Chinese 2001 (C) John Scholes jscholes@kalva.demon.co.uk 2 Jan 2003 Last corrected/updated 2 Jan 03