Understand the problem

 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$.  

Source of the problem
I.S.I. (Indian Statistical Institute) B.Stat/B.Math Entrance Examination 2019. Subjective Problem no. 7.
Topic
Polynominals (Algebra)

Difficulty Level

8 out of 10

Start with hints

Do you really need a hint? Try it first!

Do you know this lemma , 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.

Connected Program at Cheenta

I.S.I. & C.M.I. Entrance Program

Indian Statistical Institute and Chennai Mathematical Institute offer challenging bachelor’s program for gifted students. These courses are B.Stat and B.Math program in I.S.I., B.Sc. Math in C.M.I.

The entrances to these programs are far more challenging than usual engineering entrances. Cheenta offers an intense, problem-driven program for these two entrances.

Similar Problem

ISI MStat PSB 2018 Problem 1 | System of Linear Equations

This is a beautiful sample problem from ISI MStat 2018 PSB Problem 1. This is based on finding the real solution of a system of homogeneous equations . We provide detailed solution with prerequisites mentioned explicitly.

Derivative of Function Problem | TOMATO BStat Objective 757

Try this I.S.I. B.Stat Entrance Objective Problem from TOMATO based on a derivative of Function. You may use sequential hints to solve the problem.

ISI MStat PSB 2015 Question 8 | MLE & amp | Stochastic Regression

This is a problem involving BLUE for regression coefficients and MLE of a regression coefficient for a particular case of the regressors.

ISI MStat Entrance is not just an Examination. How to Prepare for it?

From the path of falling in love with data and chance. to an examination ISI MStat program is different and unique. We discuss that how ISI MStat program is something more than an exam. We will also discuss how to prepare for the exam.

ISI MStat PSB 2015 Problem 2 | Vector Space & its Dimension

This is a beautiful problem from ISI MStat 2015 PSB . We provide detailed solution with prerequisite mentioned explicitly .

Derivative of Function Problem | TOMATO BStat Objective 759

Try this TOMATO problem from I.S.I. B.Stat Entrance Objective Problem based on a derivative of Function. You may use sequential hints to solve the problem.

Discontinuity Problem | ISI B.Stat Objective | TOMATO 734

Try this beautiful problem based on Discontinuity from TOMATO 730 useful for ISI B.Stat Entrance. You may use sequential hints to solve the problem.

ISI MStat 2016 Problem 1 | Area bounded by the curves | PSB Sample

This is a beautiful problem from ISI MStat 2016 PSB (sample) Problem 1 based on area bounded by the curves. We provide a detailed solution with the prerequisites mentioned explicitly.

Derivative of Function | TOMATO BStat Objective 767

Try this TOMATO problem from I.S.I. B.Stat Entrance Objective Problem based on a derivative of Function. You may use sequential hints to solve the problem.

Kernel of a linear transformation | ISI MStat 2016 Problem 4 | PSB Sample

This is a beautiful problem from ISI MStat 2016 PSB (sample) based on Vectorspace . It uses several concepts to solve it . We provide detailed solution with prerequisites mentioned explicitly .