32nd IMO 1991 shortlist Problem 23 f(n) is an integer-valued function defined on the integers which satisfies f(m + f( f(n) ) ) = - f( f(m+1)) - n for all m, n. The polynomial g(n) has integer coefficients and g(n) = g( f(n) ) for all n. Find f(1991) and the most general form for g.
f(1991) = -1992. g(x) is a polynomial in (x 2 + x) with integral coefficients. Solution Taking m = 1, and putting f(f(2)) = k, we get f( f(f(n)) + 1) = -n - k (*). Replacing m by f(f(m)) wet get f( f(f(m)) + f(f(n)) ) = - f( f( f(f(m)) + 1) - n. We can now interchange m and n to get f( f( f(f(m)) + 1) + n = f( f( f(f(n)) + 1) + m. Using (*), this gives f(-n-k) + n = f(-m-k) - m. Replacing -n-k by n and -m-k by m we get f(n) - f(m) = m - n for all m, n. Taking m = 0 and putting h = f(0), we get f(n) = h - n for all n. Applying this to the original relation gives h - m - f(f(n)) = -f( f(m+1)) - n. Taking n = m+1, we get h = -1. Hence f(n) = -(n+1) for all n. In particular, f(1991) = -1992. We want g to satisfy g(x) = g(-x-1) for all integers x. But since g(x) is a polynomial, it must satisfy the relation for all x. Put h(x) = g(x - ½). Then h(-x) = g(-x - ½) = g(x + ½ - 1) = g(x - ½) = h(x). So h(x) has only even powers of x. Hence g(x) = h(x + ½) has only even powers of (x + ½) and hence only power of (x + ½) 2 = x 2 + x + ¼. So we can certainly write g(x) as a polynomial in (x 2 + x). Since g(x) has integral coefficients, it is an easy induction to show that when g is written as a polynomial in (x 2 + x), the coefficients must be integers. Now suppose g is any such polynomial. Since x(x+1) = (-x-1)(-x-1 +1), we have that g(x) = g(-x-1). Thus this is the most general form of g. 32nd IMO shortlist 1991 © John Scholes jscholes@kalva.demon.co.uk 2 Jan 2003 Last corrected/updated 2Jan 03