Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $P(x)$ be a polynomial in one variable with integer coefficients, and define the sequence $a_0, a_1, a_2, a_3,\cdots$ $$a_0 = 0, \ a_n = P(a_{n-1})$$ If there exists a $m$ natural number such that $a_m = 0$, then $a_1 =0 $ or $a_2 = 0$.

I have headache with this problem, my attempts go nowhere.

Can you help me?

share|improve this question
1  
Here's a start anyways: First of all, note that each $a_n$ is an integer. Thus, if $a_m=0$, $a_{m-1}$ is a root of $P$. In particular, $P$ has an integral root. By the Rational Root Theorem, this implies that either the constant term of $P$ is $0$ or a factor of the constant term is a root of $P$. However, $a_1=P(a_0)=P(0)$ is the constant term of $P$, so in the first case $a_1=0$ and we are done, so suppose instead that the constant term is nonzero and a factor of it is a root of $P$. –  Jonathan Gleason May 9 '12 at 0:51

2 Answers 2

up vote 8 down vote accepted

This is essentially a consequence of the fact that $(x - y)\mid P(x) - P(y)$. This implies that $$(a_{n+1}-a_n)\mid (P(a_{n+1})- P(a_n)) = a_{n+2} - a_{n+1}$$ for all $n\geq 0$. Thus you get that $$a_1 - a_0\mid a_2 - a_1 \mid a_3 - a_2\cdots.$$ If there is an $m$ such that $a_m = 0$, this guarantees the sequence $a_{n+1} - a_n$ is periodic. That is, you have a cycle of integers all of which divide the next. This is only possible if each of the integers is $0$ or if each of the integers is $\pm 1$. In the case they are all $0$, you get $a_1 = 0$, which is one of the posible outcomes. Suppose that all the integers are $\pm 1$. In this case, we want to conclude that $a_2 = 0$. Indeed, if $a_2\neq 0$, then either [Case 1] $a_2 = 2$ and $a_1 = 1$ or [Case 2] $a_2 = -2$ and $a_1 = -1$. Since $a_{n+1}$ can only differ by $\pm 1$ from $a_n$, the only way to have $a_m = 0$ for $m>0$ is for $a_{m-1} = 1$ (in case 1) or for $a_{m-1} = -1$ (in case 2). But if $a_{m-1} = 1$, then $a_m = P(a_{m-1}) = P(1) = a_2 = 2\neq 0,$ a contradiction. Similarly, if $a_{m-1} = -1$, then $a_m = P(a_{m-1}) = P(-1) = a_2 = -2$, a contradiction.

share|improve this answer

This is Problem A-6 on the 61st William Lowell Putnam Competition (2000); you'll find a complete set of answers to the 2000 Putnam here. (In fact solutions are available for the years 1995-2011.)

Kiran S. Kedlaya, Bjorn Poonen, Ravi Vakil, The William Lowell Putnam Mathematical Competition 1985-2000 gives another solution as well, which I adapt slightly.

Choose $m\ge 1$ minimal such that $a_m=0$. If $m=1$, we're done, so assume that $m>1$. An easy induction shows that $x_n=x_{n\,\bmod\,m}$ for all $n\ge 0$. Suppose that $0\le i<j<m$; then $$P^{m-j}(x_i)=P^{m-j}(x_j)=x_m=0\;,$$ contradicting the minimality of $m$, so the numbers $x_0,\dots,x_{m-1}$ are distinct, and in general we have $x_j=x_k$ iff $j\equiv k\pmod m$. (Here $P^n=\underbrace{P\circ P\circ\ldots\circ P}_n$.)

Now $x_j=\min\{x_0,\dots,x_{m-1}\}$ and $x_k=\max\{x_0,\dots,x_{m-1}\}$. Then $$x_k-x_j\mid P(x_k)-P(x_j)=x_{k+1}-x_{j+1}\ne 0\;,$$ since $j+1\not\equiv k+1\pmod m$. On the other hand, $x_k-x_j\ge|x_{k+1}-x_{j+1}|$ by the choice of $j$ and $k$, so $x_k-x_j=|x_{k+1}-x_{j+1}|$, and $\{x_j,x_k\}=\{x_{j+1},x_{k+1}\}$. But $x_{j+1}\ne x_j$, since $m>1$, so $x_{j+1}=x_k$, and hence $x_{j+2}=x_{k+1}=x_j$. But then $j+2\equiv j\pmod m$, so $m\mid 2$, and therefore $m=2$, as desired.

share|improve this answer
    
yes, now, i understand. I don't know about Putman, this problem give me in a contest in my country. –  d555 May 9 '12 at 2:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.