Let $f$ and $g$ be two polynomials with integer coefficients such that the leading coefficients of both the polynomials are positive. Suppose $\deg(f)$ is odd and the sets $\{f(a)\mid a\in \mathbb{Z}\}$ and $\{g(a)\mid a\in \mathbb{Z}\}$ are the same. Prove that there exists an integer $k$ such that $g(x)=f(x+k)$.
Problem
Source: Indian Team Selection Test 2015 Day 1 Problem 2
Tags: algebra, polynomial
fractals
28.08.2015 22:10
Correct me if I'm wrong, but we don't even need that $\deg(f)$ is odd...
EDIT: Indeed, we do, else the large values are attained by both positives and negatives. It's pretty much the same as below, though. First we should note that clearly $\deg(f) = \deg(g)$ by asymptotics, so both degrees are odd, and now we can continue.
Let our common set be $S$. Order its positive elements in strictly increasing order, and call them $y_1 < y_2 < \ldots$.
Now there exists $N$ such that $f(x), g(x)$ are strictly increasing and positive for $x \ge N$, since their leading coefficients are both positive.
Then their values $f(N), f(N + 1), \ldots$ and $g(N), g(N + 1), \ldots$ after a certain point identify precisely with the order of $y$; that is, $f(N) = y_k, f(N + 1) = y_{k + 1}, \ldots$ and $g(N) = y_l, g(N + 1) = y_{l + 1}, \ldots$.
Then WLOG $l \ge k$. Then $f(x + (l - k)) = f(x - N + N + (l - k)) = y_{(x - N) + k + (l - k)} = y_{x - N + l} = g((x - N) + N) = g(x)$ for all $x \ge N$.
Use the Identity Theorem to finish.
blawho12
28.08.2015 22:18
fractals wrote: Then their values $f(N), f(N + 1), \ldots$ and $g(N), g(N + 1), \ldots$ after a certain point identify precisely with the order of $y$; that is, $f(N) = y_k, f(N + 1) = y_{k + 1}, \ldots$ and $g(N) = y_l, g(N + 1) = y_{l + 1}, \ldots$.] This is only true for $odd deg(f)$.
anantmudgal09
29.08.2015 16:01
This is indeed a particular case of a problem from the Miklos Schweitzer contest(see PFTB Chapter 17 last problem)
BOBTHEGR8
19.05.2020 06:45
Solution - Call those sets as $S$ As $f$ has odd degree $S$ is not bounded below and hence $g$ also has odd degree. As $f$ and $g$ have odd degree and positive leading coefficient we cant find a $N$ such that for all $x\geq N$ we have that $f(y)<f(x) , \forall y<x$ Now chose a number $t\in S$ which is larger than $f(N)$ and $g(N)$ ( This is possible as $S$ is not bounded above) Let $t=f(m)=g(n)$ , Consider the function $h(x)=g(x+n-m)$, note that it also has same range as $g$ but $h(m)=g(n)=f(m)$ , as both $h,f$ are strictly increasing after $m$ and also all values are greater than ANY previous values we get that $h(m+1)=f(m+1), h(m+2)=f(m+2).....$ and hence $f\equiv h$ And hence $g(x)=f(x+k)$ where $k=m-n$ Hence Proved .