Maths Olympiad Prep

Library / /75 of 94

Algebra Difficulty 6.7 National Olympiad Prove it Hong Kong

Let f(x)=cmxm+cm1xm1++c1x+c0f(x) = c_m x^m + c_{m-1} x^{m-1} + \cdots + c_1 x + c_0, where each cic_i is a nonzero integer. Define a sequence {an}\{a_n\} by a1=0a_1 = 0 and an+1=f(an)a_{n+1} = f(a_n) for all positive integers nn.

a. Let ii and jj be positive integers with i<ji < j. Show that aj+1aja_{j+1} - a_j is a multiple of ai+1aia_{i+1} - a_i.

b. Show that a20080a_{2008} \neq 0.

Solution

a.
Recall the fact that bcf(b)f(c)b - c \mid f(b) - f(c) for any integers bb and cc. Putting b=ai+1b = a_{i+1} and c=aic = a_i, we immediately obtain
ai+1aif(ai+1)f(ai)=ai+2ai+1. a_{i+1} - a_i \mid f(a_{i+1}) - f(a_i) = a_{i+2} - a_{i+1}.
By induction on jj, ai+1aiaj+1aja_{i+1} - a_i \mid a_{j+1} - a_j for any j>ij > i.

b.
Suppose on the contrary that a2008=0a_{2008} = 0. Note that a2009a2008=f(0)=a2a1a_{2009}-a_{2008} = f(0) = a_2-a_1. By part (a), since a2a1ak+1aka2009a2008a_2 - a_1 \mid a_{k+1} - a_k \mid a_{2009} - a_{2008} for k=1,2,,2007k = 1, 2, \dots, 2007, each ak+1aka_{k+1} - a_k must be ±f(0)\pm f(0). Now, we have
0=a2008a1=k=12007(ak+1ak)=mf(0), 0 = a_{2008} - a_1 = \sum_{k=1}^{2007} (a_{k+1} - a_k) = m f(0),
where m{2007,2005,,1,1,3,,2007}m \in \{-2007, -2005, \dots, -1, 1, 3, \dots, 2007\}. This implies f(0)=0f(0) = 0, which contradicts the assumption that c00c_0 \neq 0. Therefore, a20080a_{2008} \neq 0.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.