ISI 2019 : Problem #7

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

w

15 users

TOPICS

No tags match your search

M

No tags match your search

M

ISI 2019 : Problem #7

G H J

Reveal topic tags

Indian Statistical Institute

Integer Polynomial

L

G H BBookmark kLocked kLocked NReply

Source: I.S.I. 2019

The post below has been deleted. Click to close.

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

3465 posts

#1 h May 5, 2019, 6:00 PM • 3 Y

Y by AK001, Adventure10, Mango247

Let $f$ be a polynomial with integer coefficients. Define $a_1 = f(0)~,~a_2 = f(a_1) = f(f(0))~,$ and $~a_n = f(a_{n-1})$ for $n \geqslant 3$ .

If there exists a natural number $k \geqslant 3$ such that $a_k = 0$ , then prove that 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.

10 posts

TCITC2

#3 h May 5, 2019, 6:38 PM • 2 Y

Y by Farbe_Bears, Adventure10

Assume $a_1 \neq 0$ and $a_2 \neq 0$ , then $a_1 | a_i$ for any natural number $i$ .
Let $t$ be the first number for which $a_t = 0$ . Then $a_t = f(a_{t-1}) = 0$ . Clearly $a_{t-1} \neq 0$ and $a_{t-1} \neq a_1$ , then there is some prime $p$ and natural number $\alpha$ such that $p^{\alpha} | a_{t-1}$ and $p^{\alpha} \nmid a_1$ . The looking at $a_t ( mod p^{\alpha} )$ we get that $a_1 \equiv 0 (mod p^{\alpha})$ which is a contradiction.

This post has been edited 1 time. Last edited by TCITC2, May 5, 2019, 7:09 PM
Reason: ...

Z K Y

The post below has been deleted. Click to close.

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

615 posts

#4 h May 6, 2019, 2:03 PM • 4 Y

Y by eriedaberrie, Euler1728, Sayan, Adventure10

Z K Y

The post below has been deleted. Click to close.

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

93 posts

#5 h May 7, 2019, 3:51 AM • 5 Y

Y by A-student, The_Maitreyo1, MathBoy23, Adventure10, Mango247

Lemma: If $p, q \in \mathbb{Z}$ and $p \neq q$ , then $p - q \mid f(p) - f(q)$ . To prove this, let $f(x) = a_nx^n + a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \cdots + a_0$ . Then $f(p) - f(q) = a_n(p^n - q^n) + a_{n-1}(p^{n-1} - q^{n-1}) + a_{n-2}(p^{n-2} - q^{n-2}) + \cdots + (p - q).$ Each bracket is divisible by $p - q$ , proving the statement.

We use the fact that the sequence $a_1, a_2, a_3, \cdots$ consists of only integers.
We'll first prove that we cannot have three distinct integers $p$ , $q$ , and $r$ such that $f(p) = q$ , $f(q) = r$ , and $f(r) = p$ (In other words, the variables cannot come in a cycle of 3). Assume that there does exist such numbers. Then we should have $p - q \mid f(p) - f(q) = q - r$ , which means $\mid p - q \mid \le \mid q - r \mid$ . Similarly we can get $\mid p - q \mid \le \mid q - r \mid \le \mid r - p\mid \le \mid p - q \mid$ , which implies equality. Ultimately, it leads to two equal variables, contradiction. In a similar manner we can prove that these variables cannot come in cycles of more than 3.

Therefore, we conclude that the variables of $f$ can only come in cycles of most two. We realize that since $a_{k+1} = f(0) = a_1$ , we have a cycle $a_1, a_2, a_3, \cdots, a_k$ . Since the minimal cycle has length at most 2, one of $a_1$ or $a_2$ must be equal to 0, and we are done.

This post has been edited 1 time. Last edited by tngkr123, May 7, 2019, 3:53 AM

Z K Y

The post below has been deleted. Click to close.

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

117 posts

#6 h Oct 27, 2019, 8:53 AM • 2 Y

Y by Adventure10, Mango247

tngkr123 wrote:

Lemma: If $p, q \in \mathbb{Z}$ and $p \neq q$ , then $p - q \mid f(p) - f(q)$ . To prove this, let $f(x) = a_nx^n + a_{n-1}x^{n-1} + a_{n-2}x^{n-2} + \cdots + a_0$ . Then $f(p) - f(q) = a_n(p^n - q^n) + a_{n-1}(p^{n-1} - q^{n-1}) + a_{n-2}(p^{n-2} - q^{n-2}) + \cdots + (p - q).$ Each bracket is divisible by $p - q$ , proving the statement.

We use the fact that the sequence $a_1, a_2, a_3, \cdots$ consists of only integers.
We'll first prove that we cannot have three distinct integers $p$ , $q$ , and $r$ such that $f(p) = q$ , $f(q) = r$ , and $f(r) = p$ (In other words, the variables cannot come in a cycle of 3). Assume that there does exist such numbers. Then we should have $p - q \mid f(p) - f(q) = q - r$ , which means $\mid p - q \mid \le \mid q - r \mid$ . Similarly we can get $\mid p - q \mid \le \mid q - r \mid \le \mid r - p\mid \le \mid p - q \mid$ , which implies equality. Ultimately, it leads to two equal variables, contradiction. In a similar manner we can prove that these variables cannot come in cycles of more than 3.

Therefore, we conclude that the variables of $f$ can only come in cycles of most two. We realize that since $a_{k+1} = f(0) = a_1$ , we have a cycle $a_1, a_2, a_3, \cdots, a_k$ . Since the minimal cycle has length at most 2, one of $a_1$ or $a_2$ must be equal to 0, and we are done.

Can anyone say if this method is correct or not?
I assumed that $a_{1} \neq 0 , a_{2} \neq 0$ first, else solving for $a_{1}$ & $a_{2}$ is not difficult. Then I proved the lemma quoted above. Now here comes my doubt : As per assumption , $(a_{k} - a_{1}) \mid (a_{k+1}-a_{2})$ and also $(a_{k} - a_{k-1}) \mid (a_{k+1}-a_{k})$ . Thus if we try $(a_{k} - a_{m}) \mid (a_{k+1}-a_{m+1})$ , where $m\geqslant 1, m\neq k$ , we see that $|a_{m}| \mid |a_{k+1}-a_{m+1}|$ .

So $|a_{k-1}| \mid |a_{k+1}|$ .

But tngkr123 said that cycles of 3 cannot come. Can we say that this is the next step, or is it conflicting with the above statement, or am I lacking something in this proof to relate with the cycles stated above?

P.S: If I'm overcomplicating things, please do tell me

This post has been edited 2 times. Last edited by A-student, Oct 27, 2019, 9:05 AM

Z K Y

The post below has been deleted. Click to close.

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

460 posts

#7 h Mar 23, 2020, 11:23 AM • 1 Y

Y by RudraRockstar

Here's a solution using the following lemma.

Lemma:

If $P\in \mathbb{Z}$ , and a sequence ${ \{ a_n \} }_n$ is defined as follows,
$a_0=0 \qquad a_n=P(a_{n-1}) \; \forall n \in \mathbb{N}$
Then, ${ \{ a_n \} }_n$ , has the following property,
$gcd(a_m,a_n)=a_{gcd(m,n)}$
Now, returning to the main problem.
According to the problem conditions, we notice ${ \{ a_n \} }_n$ , becomes periodic after some iterations.
Let, $m \in \mathbb{N}$ be the smallest natural number such that $a_m=0$ .
WLOG, we can assume that $f(0) \neq 0$ . Therefore, $m \ge 2$ .
Now, it is easy to notice that, $\not\exists \; x, y <m \; [x\neq y ]$ , such that $a_x=a_y$ .

Now, notice that $gcd(a_{m-1},a_{2m-1})=a_1$ . But as, $a_m=0$ , therefore, $a_{m-1}=a_{2m-1}$ .
Therefore we get that, $a_1=a_{m-1}$ . But as the smallest period of ${ \{ a_n \} }_n$ is $m$ , we must have $m-1=1$ .
Thus, if ${ \{ a_n \} }_n$ is non constant, we have $a_2=0$ . [ $QED$ ]

Z K Y

The post below has been deleted. Click to close.

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

296 posts

#8 h Jun 5, 2020, 4:04 AM • 1 Y

Y by Mathsolver19

Choose $m \geq 1$ minimal such that $a_{m}=0 .$ If $a_{i}=a_{j}$ for some $0 \leq i<j \leq m-1,$ then $m-j$ applications of $f$ lead to $a_{m-(j-i)}=a_{m}=0$ contradicting the minimality of $m .$ Hence, for arbitrary $i$ and $j,$ we have $a_{i}=a_{j}$ if and only if $i-j$ is divisible by $m$

If $m=1,$ we are done. Otherwise let $a_{i}>a_{j}$ be the maximum and minimum terms of $a_{0}, \ldots, a_{m-1}$ . Then $a_{i}-a_{j}$ divides $f\left(a_{i}\right)-f\left(a_{j}\right)=a_{i+1}-a_{j+1},$ which is nonzero since $(i+1)-(j+1)=i-j$ is not divisible by $m .$ On the other hand, $\left|a_{i+1}-a_{j+1}\right| \leq a_{i}-a_{j}$ because $a_{i}$ and $a_{j}$ are the maximum and minimum of all terms in the sequence. Therefore equality must occur, which implies that $a_{i+1}$ and $a_{j+1}$ equal $a_{i}$ and $a_{j}$ in some order. If $a_{i+1}=a_{i},$ then $m=1 ;$ otherwise $a_{i+1}=a_{j}$ implies $a_{i+2}=a_{j+1},$ which with $a_{j+1}=a_{i}$ yields $a_{i+2}=a_{i},$ so $m$ divides
$2$ . Hence $m$ is $1$ or
$2$
$\square$

This post has been edited 2 times. Last edited by math_and_me, Jun 5, 2020, 4:05 AM

Z K Y

The post below has been deleted. Click to close.

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

9 posts

#9 h Jul 6, 2020, 7:47 AM

Y by

assume $a_1a_2\ne0$ then let m be the smallest number such that $a_m=0$ we will prove that $a_{m-1}+a_1=0$
${a_m} - {a_1} = f\left( {{a_{k - 1}}} \right) - f\left( 0 \right) \vdots {a_{k - 1}} \Rightarrow {a_{k - 1}}|\,\,{a_{1\,}}\,\,$ (since $a_{m}=0$ )
But then, we have $|a_{m-1}|=|a_1|$ since $a_1|a_i$ so $a_{m-1}+a_1=0$
Note that $(a_1-a_0)|..|(a_{m}-a_{m-1})$ and $|a_1-a_0|=|a_m-a_{m-1}|$ the problem now is ez

This post has been edited 1 time. Last edited by nguyennam_2020, Jul 6, 2020, 7:47 AM

Z K Y

The post below has been deleted. Click to close.

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

651 posts

#10 h Jan 1, 2021, 2:30 PM • 1 Y

Y by Samujjal101

Let , $f(x) = C_n x^n +\cdots + C_1x +C_0$ .

So , $a_1 =f(0)=C_0$ .
It's not hard to see that $a_n\in \mathbb{Z}$

.i.e $a_2=f(a_1)=C_n(a_1)^n +\cdots +C_1(a_1) +a_1$
$\implies a_1\mid a_2$ (if $a_1\neq 0$

Inductively we can show $a_1\mid a_n \forall n \in \mathbb{N}$

If $a_k=0$ then $f(a_{k-1})=0$ i.e $a_{k-1}$ is root of $f(x)$ and hence $a_{k-1} \mid a_1$ .

So , $a_{k-1} =a_1$ .

So , $a_2=f(a_1)=f(a_{k-1})=a_k=0$ .

Otherwise $a_1=0$ then $a_n=0 \forall n$ .

Z K Y

The post below has been deleted. Click to close.

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

390 posts

#11 h Jan 21, 2021, 11:03 PM • 1 Y

Y by Mathmatic_lover

Let's assume $a_q=0$ is the smallest possible $q$ such that $a_r\neq 0$ for any $r<q$
We can very easily prove that there is only 2 such values of $q$ .now as $F(x)$ has all integer coefficient so $x-y|f(x)-f(y)$ is very well known fact, by using this we can very easily prove by induction that $a_1|a_r$ for every $r$ , so if $a_1=0$ then $a_r=0$ for every $r$ .hence $q=1$ is one possibility. Now if $a_1\neq 0$ and $a_2=0$ then we will have $a_{2r}=0$ for every $r$ here $q=2$ . Now if $q>2$ is odd then we will always have $a_1=0$ and $1<q$ And if $q>2$ is even then we can have $2$ possibility either $a_1=0$ or $a_2=0$ hence No more values of $q$ is possible. So we have proved that if $a_k=0$ then it is only possible if $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.

303 posts

#12 h Jan 22, 2021, 11:08 AM

Y by

integrated_JRC wrote:

Let $f$ be a polynomial with integer coefficients. Define $a_1 = f(0)~,~a_2 = f(a_1) = f(f(0))~,$ and $~a_n = f(a_{n-1})$ for $n \geqslant 3$ .

If there exists a natural number $k \geqslant 3$ such that $a_k = 0$ , then prove that either $a_1=0$ or $a_2=0$ .

As $f \in \mathbb{Z}[t]$ we've $a-b |f(a)-f(b), \, \forall a,b \in \mathbb{Z}$ then noting that by the recursive definition $a_{k-1}$ is a zero of $f$ we've the representation $f(t)=(t-a_{k-1})g(t)$ for some $g(t) \in \mathbb{Z}[t]$ .Then using previously stated result we get $a_1 |a_2 -a_1 \Leftrightarrow a_1 |a_2$ ,Then by similar divisibility arguments we can inductively extend this to $a_1 |a_k \, \forall k \in \mathbb{Z}^{+}$ Let's define $a_k=l_k a_1$ , where $l_k \in \mathbb{Z}$ and $k \in \mathbb{Z}^{+}$
Thus we get $f(a_j)=a_1 \left(l_j -l_{k-1} \right)g(a_j)$ for all $j \in \mathbb{Z}^{+}$ We note that If $a_1=0$ then $f(a_j)=0\,\, \forall j \in \mathbb{Z}$ which indeed fits the given situation, if $a_1 \neq 0$ then we again use the previously stated result to get $a_{k-1}|a_1 \Leftrightarrow l_{k-1}=1\, , a_1 =a_{k-1}$ , from which it follows that $f(a_1)=f(a_{k-1})=0=a_2$ as desired
QED

This post has been edited 3 times. Last edited by homotopygroup, Jan 22, 2021, 11:12 AM

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 Mar 27, 2023, 4:48 PM

Y by

first of all we have $f(a_{k-1})=0$ so $f(a_{k})=f(0)$ so $a_{k+1}=a_{1}$ and similarly $a_{k+2}=a_{2}$

so we have $f(x)=(x-a_{k-1})g(x)$ for some $g(x) \in \mathbb{Z}[x]$ . Then using the fact that $a_{1}|a_{2}-a_{1} \implies a_{1}|a_{2}$ , then by induction we can show $a_{1}|a_{k}$ $\forall$ $k \in \mathbb{Z^{+}}$ . so we have $f(a_{l})=a_{1}(r_{l}-r_{k-1})g(a_{l})$ , so if $a_{1}=0$ we get that $f(a_{l})=0$ $\forall$ $l \in \mathbb{Z^{+}}$ . sps that $a_{1} \neq 0$ , then we proceed like this:

$a_{2}-a_{1}|a_{3}-a_{2}|\cdots |a_{n}-a_{n-1}|\cdots |a_{k+1}-a_{k} | a_{1}$ since $a_{k}=0$ and $a_{k+1}=a_{1}$

also we notice that $a_{2}=f(a_{1}) \equiv f(0) \pmod{a_{1}}$ which gives $a_{2}-a_{1} \equiv 0 \pmod{a_{1}}$ , hence we have $a_{1}|a_{2}-a_{1}|a_{3}-a_{2}|\cdots |a_{n}-a_{n-1}|\cdots |a_{k+1}-a_{k} | a_{1}$ , which gives $a_{2}-a_{1}=\pm a_{1} , a_{3}-a_{2}=\pm a_{1} , \cdots , a_{k+1}-a_{k}=\pm a_{1}$

now we observe that $\sum_{i=1}^{k} a_{i}-a_{i-1}=a_{k} =0$ , which gives that we must have at least a $\ell$ s.t. $a_{\ell}-a_{\ell-1}=-(a_{\ell+1}-a_{\ell})$ hence we get that $a_{\ell-1}=a_{\ell+1}$ , take over $f$ until we get $\implies a_{k}=a_{k+2}=a_{2}$ which proves $a_{2}=0$ and done $\blacksquare$

This post has been edited 6 times. Last edited by lifeismathematics, Mar 27, 2023, 6:12 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a