Find the least positive number m such that for any polynimial f(x) with real coefficients, there is a polynimial g(x) with real coefficients (degree not greater than m) such that there exist 2017 distinct number $a_1,a_2,...,a_{2017}$ such that $g(a_i)=f(a_{i+1})$ for i=1,2,...,2017 where indices taken modulo 2017.
Problem
Source: 2017 China TST 5 P2
Tags: algebra, polynomial, abstract algebra
09.04.2017 06:07
The key is to figure out the solution for $f(x) = x$ and have the audacity to generalize that. Just as another hint, don't think too hard about polynomials.
14.04.2017 06:36
Does anyone have a full solution to this problem? Thanks!
15.04.2017 21:27
First prove that a quadratic $g$ works for $f(x)=x$ and then generalize to any $f$.
12.08.2017 14:32
Can anyone give a full solution to this Thanks?
12.08.2017 16:32
Suppose we have such a f. Pick your top 2017 favorite numbers(which is just another way of saying they don't matter) and apply the Lagrange Interpolation Formula and the defining equation to find g. Does this count as a sol?
16.03.2020 18:50
duck_master wrote: ... This only shows the existence of $m$ but does not find it. We claim that $m = 2$. To see that $m = 1$ will not work, suppose we have some linear $g(x) = ax + b$ satisfying this condition and $f(x) = x$. Then $\max a_i \max f(a_i) = \max g(a_i) = g(\max a_i)$ and similarly for minimum, hence $g(x) = x$, contradiction. Now for any $f$, pick an interval $[M,\infty)$ over which $f$ is strictly increasing (or strictly decreasing, but the two cases can be dealt with the same way). Pick two points $(x_1, f(x_1)), (x_2,f(x_2))$ with $23333M^{23333} < x_1 < x_2$, then choose some concave quadratic $g$ that passes through these two points. For some suitable $g$, we will choose $r \in (x_1,x_2)$ such that $g(r) > f(x_2) > f(x_1) > gf^{-1}g(r)$ (if this cannot be done then decrease the curvature of $g$. Write $g(x) = ax^2 + bx + c$, as $a\to -\infty, g(x) \to a(x-\frac{x_1 + x_2}{2})^2 + f(x_1)$, then choosing $r = \frac{x_1 + 2x_2}{3}$ we see that $g(r) \to \infty, f^{-1}g(r) \to \infty, gf^{-1}g(r) \to -\infty$ as well). After this we construct the following sequence: $r_0 = r,$ and for each $i\ge 1$ let $r_i$ the unique real number within $(x_1, x_2)$ such that $g(r_i) = f(r_{i-1})$. This infinite sequence is decreasing, approaches but always stays above $x_1$. Our problem would be solved if we can find $a_1$ such that $(f^{-1}g)^{(2017)}(a_1) = a_1$ and $(f^{-1}g)(a_1) \ne a_1$. In our case it suffices to find such $a_1$ between $x_1, x_2$ (which are the only two fixed points of $f^{-1}g(x)$). Note that $f^{-1}g$ is continuous over this interval, $(f^{-1}g)^{(2017)}(r_{2016}) = (f^{-1}g)(r_0) > f^{-1}(f(r_0)) = r_0 > r_{2016}$ and $(f^{-1}g)^{(2017)}(r_{2015}) = (f^{-1}g)^2(r_0) < f^{-1}g(x_1) = x_1 < r_{2015}$. Thus there actually exists $x \in (r_{2016},r_{2015}) \subset (x_1,x_2)$ with $f^{-1}g(x) = 0$ by intermediate value theorem, as desired.