Find all positive integers $n$ and sequence of integers $a_0,a_1,\ldots, a_n$ such that the following hold: 1. $a_n\neq 0$; 2. $f(a_{i-1})=a_i$ for all $i=1,\ldots, n$, where $f(x) = a_nx^n+a_{n-1}x^{n-1}+\cdots +a_0$. Proposed by usjl
Problem
Source: 2024 Taiwan TST Round 3 Mock P6
Tags: Taiwan, polynomial, Sequence, algebra
02.05.2024 13:55
bump!!!!
03.05.2024 09:52
bump!!!!!!!!!!!!!!!
05.05.2024 11:51
I have found $f(x)=-2x+2$ and $f(x)=-x^{2k}-x^{2k-1}-\cdots-x-1$ works.
05.05.2024 16:28
toshihiro shimizu wrote: I have found $f(x)=-2x+2$ and $f(x)=-x^{2k}-x^{2k-1}-\cdots-x-1$ works. Those are not the only ones
07.05.2024 15:21
I also found $f(x)=3x^2+x-1$. I have some progress in mathematical consideration but it is very complicated... I used computer to find the answer based on it. I am checking that consideration to simplify.
01.07.2024 10:42
Case 1: $n=1$. Let $f(x)=ax+b$, so $f(b)=ab+b=a$. Thus $b=\frac{a}{a+1}$, and since $a,b$ are integers we get that $a=-2,b=2$. Case 2: $n=2$. Let $f(x)=ax^2+bx+c$, then $f(c)=ac^2+bc+c=b$ and $f(b)=ab^2+b^2+c=a$ which can be checked. Case 3: $n\ge 3$. If $a_n\ge 2$ and there exists $i<n$ such that $\vert a_i\vert\ge 2$, by taking $i$ such that $\vert a_i\vert$ is maximum, it's easy to get that $f(a_{n-1})>a_n$ because of growth and it's a contradiction. If $a_n\le -2$ and there exists $i<n$ such that $\vert a_i\vert\ge 2$, by doing the same approach as above, it's a contradiction. If $\vert a_n\vert\ge 2$ but there does not exist such $i<n$, we get that $a_i=\pm 1, 0$ but if $a_i=0$, since $a_{i+1}=f(a_i)=f(0)=a_0$, we get a contradiction since there exists $j<n$ such that $a_j=a_n$. Now its the case that $a_i=\pm 1$ for $i<n$ and $\vert a_n\vert\ge 2$, if $a_{n-1}=1$ we get that $a_i=-1$ for $i<n-1$, again it's a contradiction for $n>2$ since $1=f(-1)=-1$, and if $a_{n-1}=-1$, by the same approach it's a contradiction. So we get that $a_n=\pm 1$. If $a_n=\pm1$ and for some $i$ we have $\vert a_i\vert>1$ you can easily see that it's a contradiction (again by growth). Now we have to check the case that $a_i=\pm 1,0$ for all $i$. I didn't check this case, but I don't think it's a hard one.
24.08.2024 20:51
Interesting problem! Here is a sketch with more details inspired by the posts from toshihiro shimizu and ayeen_izady. Hopefully I did not make a mistake The solutions are $f(x)=2x-2$, $f(x)=3x^2+x-1$, and $f(x)=-x^{2k}-x^{2k-1}-\dots-x-1$. First we resolve the cases $n=1$ and $n=2$. For $n=1$ we are left with $f(a_0)=a_1\cdot a_0+a_0=a_0(a_1+1)=a_1$ which gives $(a_0,a_1)=(2,-2)$. For $n=2$ let $a=a_2$, $b=a_1$, and $c=a_0$ for convenience, we have that $$ac^2+bc+c=b\Rightarrow c|b$$$$ab^2+b^2+c=a\Rightarrow c|a$$So let $a=ca'$ and $b=cb'$ giving $$a'c^2+b'c+1=b'$$$$a'b'^2c^2+b'^2c+1=a'$$Notice $b'\neq 0$ and $a\neq 0\Rightarrow c\neq 0$. The second equation then gives $$\frac{a'-1}{c(a'c+1)}=b'^2$$from which it is not hard to conclude that $c=-1$. This gives $b'=-1\Rightarrow a'=-3$ so we get $(a_0,a_1,a_2)=(-1,1,3)$. Now we look at the case $a_i=a_j$ for some $0\leq i< k \leq n$. But it is well known that if a number is periodic under $f$ then it must have minimum period $1$ or $2$ say alternating between $a$ and $b$ (notice however that $a_i$ need not start periodic). If one $a_i=0$ then $a_{i+1}=a_0$ so $a_i$ must be periodic from the beginning and alternate between $a_0$ and $0$. Thus we must have $f(a_0)=$ $a_0+a_0^3+\dots +a_0^{2k+1}=0$ which is impossible. So assume for the rest of the solution that the $a_i$ are non-zero. Notice that we have that $a_0\neq 0$, $a_0$ divides all $a_i$ by induction, and $a_i|a_{i+1}-a_0$. Thus let $a=a_0 a'$ and $b=a_0 b'$ so we get that $a'|b'-1$ and $b'|a'-1$. If $a'$ or $b'$ is $1$ then $a_i$ was periodic from the beginning which we will handle later. Otherwise $(a',b')=(-1,2)$, $(a',b')=(-1,-1)$, or permutation. Notice that $f(a_i)$ is the sum of multiples of $a_0^2$ plus a final $a_0$ so we have that $a_0=\pm 1$. Since $a_i$ was not periodic from the beginning we must have $a_0=1$. If $(a,b)=(-1,2)$ then $2|f(1)+f(-1)=2+f(1)$ so $f(1)$ must be even. Thus $f(2)$ is the sum of multiples of $4$ plus $1$, a contradiction. If $(a,b)=(-1,-1)$ then we must have $f(x)=-1$ for some $x\neq -1$ so $1\equiv -1\pmod{x}$ which would give $x=1,2,-2$ but as $a_i$ is not periodic from the begging we must have $x=\pm 2$. For the same reason as above, $f(1)$ must be odd but $2|f(1)+f(-1)=\pm 2+-1$, a contradiction. Thus we are left to deal with $f$ alternating between $a$ and $b$. Assume that $a_0=a$. If $n$ is odd then we have $f(a)=(b+1)(a^{2k+1}+a^{2k-1}+\dots+a)=b$ which gives a solution of $(a,b,k)=(1,-2,1)$ which fails for the other direction. If $n$ is even then $f(b)=(a+1)(b^{2k}+b^{2k-2}+\dots+1)-1=a$. If $a=-1$ the other direction gives $b=-1$ which works. Otherwise, $b^{2k}+b^{2k-2}+\dots+1=1$ which is impossible. Now we have that all $a_i$ are distinct and non-zero and $n>2$. As above $a_{i-1}-a_{j-1}|a_i-a_j$. Choosing $|a_i-a_j|$ maximal we must have either $i=0$ or $j=0$ or we get a contradiction. Thus $a_0$ is either a maximum or minimum of $a_i$ so all the $a_i$ for $i>0$ have the same sign. Now let $|M|$ be the maximum of $|a_i|$. First assume that $i<n$. Then $$|f(M)|=|a_nM^n+\dots+a_1M+a_0|\geq |a_n M^n|-|a_{n-1}M^{n-1}|+|a_{n-2}M^{n-2}|-\dots $$using the fact that all $a_i$ for $i>0$. It is not hard to bound the below by $M$ using that $a_i$ are all at most $M$ and distinct for $i>0$ and pairing up adjacent terms. Thus $|a_n|$ is maximal. But plugging in the positive one in $a_0$ or $a_1$ gives that either $|a_1|$ or $|a_2|$ is larger than $|M|$, a contradiction.