Putnam 2000 A6

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

w

2 users

TOPICS

No tags match your search

M

No tags match your search

M

Putnam 2000 A6

G H J

Reveal topic tags

modular arithmetic

Rational Root Theorem

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

6294 posts

#1 h Sep 6, 2011, 10:22 PM • 3 Y

Y by Rounak_iitr, Adventure10, Mango247

Let $f(x)$ be a polynomial with integer coefficients. Define a sequence $a_0, a_1, \cdots$ of integers such that $a_0=0$ and $a_{n+1}=f(a_n)$ for all $n \ge 0$ . Prove that if there exists a positive integer $m$ for which $a_m=0$ then either $a_1=0$ or $a_2=0$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Kent Merryfield

18574 posts

Kent Merryfield

#2 h Sep 7, 2011, 12:54 AM • 9 Y

Y by FinalSix, skrublord420, Centralorbit, math_and_me, Arkajit_Ganguly, Adventure10, Mango247, and 2 other users

If $a_1 = 0,$ then $a_n = 0\ \forall\, n$ and we are done. In all that follows, assume $a_1 \ne 0.$

Let $N$ be the smallest positive integer for which $a_N = 0.$ That there is such an N comes from the hypothesis of the problem that the sequence eventually reaches $0$ and from the well-ordering of the natural numbers. By our assumption, $N \ge 2.$

If for any $k < m, a_k = a_m,$ then for all $n > m,$ if we find that $s, k \le s < m,$ for which $n \equiv s \pmod {(m - k)},$ then $a_n = a_s.$ In other words, from that point on, the sequence $a_n$ is periodic of period $m - k.$ This follows from the fact that each $a_n$ depends only on its predecessor and an induction.

It now follows that we cannot have $a_k = a_m$ for any $0 < k < m < N,$ since if that did occur, the sequence would repeat only those values of $a_n$ for $k \le n < m,$ none of which are zero.

We observe that if $f$ is an integer-coefficient polynomial and $x$ and $y$ are integers, then $(x - y)\, |\, (f(x) - f(y)).$ This follows by induction and linearity from the fact that for each integer power $k, (x - y)\, |\, (x^k - y^k).$ This is clear for $k = 0$ and $1,$ and for larger $k,$ $(x_k - y_k) = (x - y)(x^{k-1} + x^{k-2}y + \cdots + y^{k-1}).$ Then, since $a_{n+2} - a_{n+1} = f(a_{n+1}) - f(a_n),$ we have that for all $n \ge 0,$ $(a_{n+1} - a_n)\, |\, (a_{n+2} - a_{n+1}).$ Each difference divides the next difference. None of these differences are zero (by the previous $a_k \ne a_m$ argument) but since the sequences are periodic, the differences are periodic. That means that no difference can ever be bigger (in absolute value) than any other difference: they are all, except possibly for sign, the same. Since the first difference is $a_1,$ all differences are $\pm a_1.$ That means that the sequence $a_n$ “walks” one step at a time, backwards or forwards, over the set of integer multiples of $a_1.$ This walking sequence starts at $0$ and must return to $0.$ However, from the $a_k \ne a_m$ argument, this sequence can never retrace any steps on the way from 0 to 0, and that means that it can never get two steps away from 0. Its first step is to $a_1;$ its next step cannot be to $2a_1$ so it must be back to $0.$ Hence, $a_2 = 0,$ which is what we were trying to prove.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4216 posts

#3 h Apr 17, 2014, 12:24 AM • 3 Y

Y by Euler1728, tuanngoc298, Adventure10

Notice that $a_n=f^n(0)$ and $a_0=0$ . Since $f^{m}(0)=f(f^{m-1}(0))=0$ , we must have $f^{m-1}(0)$ to be a root of $f(x)$ . Call this root $r$ . Also call the constant term of $f$ , $c_0$ and notice that $f(0)=c_0$ .

There are two cases, where $c_0=0$ and where $c_0\neq 0$ . If $c_0=0$ then $a_1=f(0)=c_0=0$ and we are done. If $c_0\neq 0$ , we proceed as follows.

Notice that $c_0 | f(kc_0)$ where $k\in \mathbb{Z}$ since $f$ has integer coefficients. Then we have
$c_0 | f(0)=c_0$
so
$c_0 | f(0) | f(f(0)) | \cdots | f^{m-1}(0) = r$
Hence $c_0|r$ . However, since $r$ is clearly an integer, by the rational root theorem, $r|c_0$ and thus we have $c_0=r$ . Therefore, $a_2 = f(f(0))=f(c_0)=f(r)=0$ .

Therefore, either $a_1=0$ or $a_2=0$ as desired.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

756 posts

#4 h Apr 26, 2018, 2:49 PM • 3 Y

Y by GreenKeeper, Adventure10, Mango247

Nice Problem.
Here is my solution:
$\longrightarrow$ Since $f(x)$ is an integer polynomial, we use the fact that $m-n| f(m)-f(n) \forall m,n \in \mathbb{Z}$ .

Let $b_n =^{DEF} a_{n+1}-a_n$ . Then, $b_n | b_{n+1} \forall n$ .

On the other hand, we are given that $a_0 = a_m = 0$ so $a_n$ is cyclic after m terms and so $b_0 = b_m$ .

If $b_0 =0$ , then $a_i = a_j \forall i,j\in (0,1,2,\dots,m)$ and we are done. Otherwise $|b_0| = |b_1| =\dots$

So $b_n = b_0$ or $b_n = - b_0$ and from here the conclusion follows easily.

This post has been edited 1 time. Last edited by e_plus_pi, Apr 26, 2018, 2:50 PM
Reason: Spacing

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

18 posts

#5 h Jul 1, 2019, 8:27 PM • 1 Y

Y by Adventure10

Thanks a lot

This post has been edited 1 time. Last edited by Luta_Tnana, Jul 1, 2019, 8:31 PM
Reason: I understood it later

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

18 posts

#6 h Jul 1, 2019, 8:30 PM • 1 Y

Y by Adventure10

Oh I get ya ! Sorry

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

375 posts

#7 h Jul 1, 2019, 8:30 PM • 1 Y

Y by Adventure10

ahaanomegas wrote:

Let $f(x)$ be a polynomial with integer coefficients. Define a sequence $a_0, a_1, \cdots$ of integers such that $a_0=0$ and $a_{n+1}=f(a_n)$ for all $n \ge 0$ . Prove that if there exists a positive integer $m$ for which $a_m=0$ then either $a_1=0$ or $a_2=0$ .

This is a question of ISI 2019

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

18 posts

#8 h Jul 1, 2019, 8:31 PM • 1 Y

Y by Adventure10

Ya it is !!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

28 posts

Raunii

#11 h Mar 20, 2020, 4:02 PM

Y by

JSGandora wrote:

Notice that $a_n=f^n(0)$ and $a_0=0$ . Since $f^{m}(0)=f(f^{m-1}(0))=0$ , we must have $f^{m-1}(0)$ to be a root of $f(x)$ . Call this root $r$ . Also call the constant term of $f$ , $c_0$ and notice that $f(0)=c_0$ .

There are two cases, where $c_0=0$ and where $c_0\neq 0$ . If $c_0=0$ then $a_1=f(0)=c_0=0$ and we are done. If $c_0\neq 0$ , we proceed as follows.

Notice that $c_0 | f(kc_0)$ where $k\in \mathbb{Z}$ since $f$ has integer coefficients. Then we have
$c_0 | f(0)=c_0$ so
$c_0 | f(0) | f(f(0)) | \cdots | f^{m-1}(0) = r$ Hence $c_0|r$ . However, since $r$ is clearly an integer, by the rational root theorem, $r|c_0$ and thus we have $c_0=r$ . Therefore, $a_2 = f(f(0))=f(c_0)=f(r)=0$ .

Therefore, either $a_1=0$ or $a_2=0$ as desired.

it may happen that $c=-r$ then what? wont we have to take cases

This post has been edited 1 time. Last edited by Raunii, Mar 20, 2020, 4:03 PM
Reason: ,

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

77 posts

#12 h Nov 16, 2020, 7:21 PM

Y by

I agree with @above. I tried the same approach as @JSGandora with the rational root theorem, but was eventually stuck on the case $c = -r$ .

I believe that the only way to resolve this is through the the differences / integer divisibility approach.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lifeismathematics

1188 posts

lifeismathematics

#14 h Oct 2, 2023, 2:44 PM

Y by

define $d_{i}=a_{i+1}-a_{i}$

Now since $f(x) \in \mathbb{Z}[x]$ , we have $a_{i+1}-a_{i}|f(a_{i+1})-f(a_{i}) =a_{i+2}-a_{i+1}=d_{i+1}$

so we have $d_{i}|d_{i+1}$ $\forall$ $i \geqslant 0$

now we also have $a_{m}=0$ for some $m \in \mathbb{Z}^{+}$ , so $a_{m}=a_{0}$ , and $a_{m+1}=a_{1}$ , hence we have $d_{m}=d_{0}$

hence we have $|d_{0}|=|d_{1}|=|d_{2}|=\cdots =|d_{i}|=\Omega$ for $i \geqslant 0$

Now:

if $\Omega=0$

so we have $a_{1}=0$ .
if $\Omega \neq 0$

so we have that the set $\{ a_{1} , a_{2} , \cdots , a_{m}\} \subseteq \mathbb{Z}^{+}_{0}$ , hence by well ordering principle this set has a minimum. say $a_{\ell}$ , so $a_{\ell-1}>a_{\ell}$ , $a_{\ell+1}>a_{\ell}$ , so we have $d_{\ell-1}=-d_{\ell} \implies a_{\ell-1}=a_{\ell+1}$ , now we can take $f$ over until we get $a_{2}=a_{0}=0$ , or if not then we have $f(a_{\ell-2})=f(a_{\ell})\implies a_{\ell-2}=a_{\ell}$ so we do this until we get $a_{2}=a_{0}=0$

Hence either $a_{1}=0$ or $a_{2}=0.$ $\blacksquare$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chakrabortyahan

385 posts

chakrabortyahan

#15 h May 3, 2024, 5:54 PM

Y by

Lol isi 2019 problem...(not nearly a A6 though) in 2nd page there is a typo it would be $f(d)=2d,f(2d) = d$ ...and there was a third page with the line "Hence $a_2 = 0$ if $a_1\neq 0$ "
$\blacksquare\smiley$

Attachments:

This post has been edited 1 time. Last edited by chakrabortyahan, May 3, 2024, 5:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

947 posts

#16 h May 5, 2024, 11:34 AM

Y by

Storage purposes only... one of my most favorite problems :-D

:-D

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PRMOisTheHardestExam

409 posts

PRMOisTheHardestExam

#17 h May 5, 2024, 4:26 PM

Y by

lemma in imo 2006 p5

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

302 posts

#18 h Sep 19, 2024, 6:06 AM

Y by

We prove the following generalisation:
If a polynomial $f(x) \in \mathbb{Z}[x]$ has a degree $n$ fixed point $a$ , then $n=1$ or $2$ .

Assume FTSOC that $n>2$ .
Note that for all integers $x \neq y$ , we have $x-y \mid f(x)-f(y)$ .
Let $x_i=f^i(a)-f^{i-1}(a)$ for all positive integers $i$ , so $x_{n+i}=x_{i}$ . Then we have $x_2 \mid x_3 \mid \cdots \mid x_{n+2} = x_2$ , from which we see that $\left| x_i \right|$ is a nonzero constant for all positive integers $i$ .
Note that $x_1=x_2$ since $n>2$ , and $\sum_{i=1}^n x_i =0$ . Since it is not possible that $x_i$ is constant, let $k$ be the smallest positive integer such that $x_{k+2}=-x_1$ .
Then we have $f^{i}(a) = ix_1 + a$ for all $1 \leq i \leq k+1$ and $f^{k+2}(a)= kx_1+a = f^k(a)$ .
It follows that $f^{k+m}(a) = \begin{cases} f^k(a)=kx_1+a & \text{if } m \text{ is even} \\ f^{k+1}(a)=(k+1)x_1+a &\text{if } m \text{ is odd} \end{cases}$ for all nonnegative integers $m$ , so $f^m(a) \neq a$ for all positive integers $m$ , which contradicts the fact that $f^n(a)=a$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

244 posts

#19 h Apr 6, 2025, 1:35 PM

Y by

Define:= $b_{n}=a_{n+1}-a_{n}$
Lemma 1: if $f(x) \in \mathbb{Z}[x]$ then $x-y \mid f(x)-f(y)$ $\forall x,y \in \mathbb{Z}$

Coming back to the problem,
$f(a_{m})=a_{m+1}$
$f(0)=a_{m+1}$
we know $f(a_{0})=a_{1}$
$f(0)=a_{1}$
$a_{1}=a_{m+1}$
Similarly by induction we can show that $a_{m}=a_{m+k}$ $\forall k \in \mathbb{N}_{0}$
$\therefore$ $(a_{n})_{n\geq 1}$ is a cyclic sequence in $m$ terms

Since we know that the sequence $(a_{n})_{n \geq 1}$ is an integer sequence therefore Lemma 1 is applicable to all the terms in the sequence

Now,
$a_{n+1}-a_{n} \mid f(a_{n+1})-f(a_{n})$
or, $b_{n} \mid b_{n+1}$

from the fact that $a_{n}$ is a cyclic sequence in $m$ terms notice that $b_{m}$ is cyclic in $m$ terms,

$\therefore$ | $b_{0}$ |=| $b_{m}$ |

We know that $b_{n} \mid b_{n+1}$ and $(b_{n})_{n\geq 1}$ is a cyclic sequence in $m$ terms

therefore $|b_0| = |b_1| =\dots$

Case 1:

$b_0 =0$

Then $a_i = a_j \forall i,j\in (0,1,2,\dots,m)$ and we are done

Case 2:

$|b_0| = |b_1| =\dots$ $= \alpha$

$b_n = b_0$ or $b_n = - b_0$

$a_{n+1}-a_{n}=a_{1}$ or $a_{n+1}-a_{n}=-a_{1}$
Hence, the conclusion follows $\mathbb{Q.E.D}$ $\blacksquare$
:whistling:

:whistling:

This post has been edited 2 times. Last edited by Levieee, Apr 6, 2025, 1:37 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a