2nd Chinese 1987 Problem B3 A set of distinct positive integers has sum 1987. What is the maximum possible value for three times the total number of integers plus the number of odd integers?
1 + 2 + ... + 62 = 62·63/2 = 1953, 1 + 2 + ... + 63 = 63·64/2 = 2016. So we can find at most 62 distinct integers with sum 1987. We can take 35 of these to be odd and 27 even without penalty: 1 + 2 + ... + 54 (so far 27 of each) + 55 + 57 + 59 + 61 + 63 + 65 + 67 + 69 = 1981. But if we increase the number of odd any further we must decrease the total number (replacing 54 by 71 is an increase of 17). If we replace 4 even numbers we cannot replace them by 3 odd numbers (71 + 73 + 75 - 54 - 52 - 50 - 48 = 15 > 6). So this is the best we can do. To get a total actually equal to 1987 just increase one of the odd numbers by 6, eg 75 instead of 69. That gives 4·35 + 3·27 = 221. The argument that 221 is optimal is perhaps not entirely convincing. So suppose we have m odd numbers and n even numbers. The total of the odd numbers cannot be less than the sum of the first m odd numbers which is m 2 and the sum of the even numbers cannot be less than the sum of the first n even numbers which is n(n+1). So we must show that if 4m + 3n >= 222, then m 2 + n(n+1) > 1987. But 4m + 3n ≥ 222 implies 4m + 3(n + 1/2) ≥ 223 1/2 and hence, by Cauchy-Schwartz, 5√(m 2 + (n+ 1/2) 2 ) > 223 1/2, so m 2 + n 2 + n > (447/10) 2 - 1/4 > 1987. 2nd Chinese 1987 © John Scholes jscholes@kalva.demon.co.uk 11 Apr 2002