61st Putnam 2000 Problem A6 p(x) is a polynomial with integer coefficients. A sequence x 0 , x 1 , x 2 , ... is defined by x 0 = 0, x n+1 = p(x n ). Prove that if x n = 0 for some n > 0, then x 1 = 0 or x 2 = 0.
Solution
If x 1 = 0, then obviously all x n = 0. So that is one possibility. Assume, then, that x 1 is non-zero. Assume also that x N = 0 for some N > 1. Then x N+1 = p(0) = x 1 . a - b always divides a s - b s and hence also p(a) - p(b). So x n+1 - x n divides x n+2 - x n+1 . But x N+1 - x N = x 1 - x 0 . So for all 0 <= n <= N, we have x n+1 - x n = ±x 1 . Moreover, some signs must be positive and some negative, since (x 1 - x 0 ) + (x 2 - x 1 ) + ... + (x N - x N-1 ) = x N - x 0 = 0. So we must be able to find an adjacent pair of opposite signs: x n+1 - x n = -(x n - x n-1 ), with 1 ≤ n ≤ N. Hence x n-1 = x n+1 . But now p(x n-1 ) = p(x n+1 ), or x n = x n+2 . So by a simple induction x N = x N+2 . But x N = 0, and x N+2 = x 2 , so x 2 = 0, as required. 61st Putnam 2000 © John Scholes [email protected] 1 Jan 2001
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.