IMO 1976 SL 12

Origin: VIE

Problem

The polynomial 1976(x+x2+\cdot \cdot \cdot+xn) is decomposed into a sum of polynomials of the form a1x + a2x2 + . . . + anxn, where a1, a2, \cdot \cdot \cdot , an are distinct positive integers not greater than n. Find all values of n for which such a decomposition is possible.

Solution

Suppose the decomposition into k polynomials is possible. The sum of coefficients of each polynomial a1x + a2x2 + \cdot \cdot \cdot + anxn equals 1 + \cdot \cdot \cdot + n = n(n + 1)/2 while the sum of coefficients of 1976(x + x2 + \cdot \cdot \cdot + xn) is 1976n. Hence we must have 1976n = kn(n + 1)/2, which reduces to (n+1) | 3952 = 24\cdot13\cdot19. In other words, n is of the form n = 2\alpha13\beta19\gamma−1, with 0 \leq\alpha \leq4, 0 \leq\beta \leq1, 0 \leq\gamma \leq1. We can immediately eliminate the values n = 0 and n = 3951 that correspond to \alpha = \beta = \gamma = 0 and \alpha = 4, \beta = \gamma = 1. We claim that all other values n are permitted. There are two cases. \alpha \leq3. In this case k = 3952/(n + 1) is even. The simple choice of the polynomials P = x+2x2+\cdot \cdot \cdot+nxn and P ′ = nx+(n−1)x2+\cdot \cdot \cdot+xn suffices, since k(P + P ′)/2 = 1976(x + x2 + \cdot \cdot \cdot + xn). \alpha = 4. Then k is odd. Consider (k −3)/2 pairs (P, P ′) of the former case and P1 = / nx + (n −1)x3 + \cdot \cdot \cdot + n+1 2 xn0 + / n−1 2 x2 + n−3 2 x4 + \cdot \cdot \cdot + xn−10 ; P2 = / n+1 2 x + n−1 2 x3 + \cdot \cdot \cdot + xn0 + / nx2 + (n −1)x4 + \cdot \cdot \cdot + n+3 2 xn−10 . Then P + P1 + P2 = 3(n + 1)(x + x2 + \cdot \cdot \cdot + xn)/2 and therefore (k −3)(P + P ′)/2 + (P + P1 + P2) = 1976(x + x2 + \cdot \cdot \cdot + xn). It follows that the desired decomposition is possible if and only if 1 < n < 3951 and n + 1 | 2 \cdot 1976.