Suppose $f$ is a polynomial in $\mathbb{Z}[X]$ and m is integer .Consider the sequence $a_i$ like this $a_1=m$ and $a_{i+1}=f(a_i)$ find all polynomials $f$ and alll integers $m$ that for each $i$: \[ a_i | a_{i+1}\]
Problem
Source: Iran 2004
Tags: algebra, Integer Polynomial, Integer sequence
15.09.2004 04:40
This is really weird. Are you sure all of them can be found and presented in a nice way? $a_i|a_{i+1}=f(a_i)$ is equivalent to $a_i|f(0)$. First of all, all polynomials for which $f(0)=0$ and all numbers $m\in\mathbb Z$ are Ok. Now assume $f(0)\ne 0$. This means that $\{a_i\}$ has only finitely many values, so from some point on it becomes periodic. Another thing we can observe is that $a_i\ne 0$ because then nothing would make sense. If the period the sequence eventually gets is $>2$, then we get a contradiction, because there must be some $i$ for which $|a_i|>|a_{i+1}|$. Now there are two cases left: 1) For $n\ge n_0$ we have $f(a_n)=-a_n$; 2) For $n\ge n_0$ we have $f(a_n)=a_n$. I have no idea if there's a nice way to classify all these polynomials (and $a_1$s). We know one thing: in the first case $f(x)+x$ must have both $k$ and $-k$ as roots for some integer $k$, and in the second case $f(x)-x$ must have at least an integral root.
21.05.2008 14:54
I can't find any question of this sort in Iran NMO (Round 1/2/3).. Is it Iran TST 2004? or is this question just wrong? As grobber mentioned, I doubt there could possibly be a clear formula for the solution.. [Edit] I think this is the solution: (i) For all $ f$ with integer coefficients such that $ f(0)=0$: m can be any integer. (ii) If $ f(0) \neq 0$, then $ f(f(x)) = x$ must yield an integer solution. $ m$ must be an integer solution of the equation $ f(f(x))=x$. (The proof for the (ii) part involves the following lemma - if a polynomial $ f$ satisfies $ f^k (a) = a$ for some integer $ a$ and some natural number $ k$, then $ f$ must satisfy $ f(f(a)) = a$ - which is easy (something similar to this was on the USAMO))
28.08.2016 09:33
after 12 year and It have't a full solution :
26.10.2017 13:22
BumpBump
11.11.2017 16:38
Again Bump
12.07.2024 18:22
Bump after 20 years...