Let $n,m$ be positive integers such that $n<m$ and $a_1, a_2, ..., a_m$ be different real numbers. (a) Find all polynomials $P$ with real coefficients and degree at most $n$ such that: $|P(a_i)-P(a_j)|=|a_i-a_j|$ for all $i,j=\{1, 2, ..., m\}$ such that $i<j$. (b) If $n,m\ge 2$ does there exist a polynomial $Q$ with real coefficients and degree $n$ such that: $|Q(a_i)-Q(a_j)|<|a_i-a_j|$ for all $i,j=\{1, 2, ..., m\}$ such that $i<j$ Edit: See #3
Problem
Source: 2018 Greece National Olympiad Problem 3
Tags: algebra, polynomial, absolute value
ThE-dArK-lOrD
03.03.2018 23:05
Note that the condition can be written as $|P(a_i)-P(a_j)|=|a_i-a_j|$ for all $i,j\in \{ 1,2,...,m\}$. So, we can WLOG $a_1<a_2<...<a_m$.
We can prove by induction on $\ell \in \{ 1,2,...,m\}$ that:
Quote:
Either $P(a_i)-P(a_j)=a_i-a_j$ for all $i,j \in \{ 1,2,...,\ell\}$ or $P(a_i)-P(a_j)=-(a_i-a_j)$ for all $i,j \in \{ 1,2,...,\ell\}$.
We use the result when $\ell \leftarrow m$.
In the former case, we get that the polynomial $P(x)-x -(P(a_1)-a_1)$ with degree at most $n$ has at least $m$ distinct roots, namely $a_1,a_2,...,a_m$.
This is clearly impossible unless it's zero polynomial, i.e. $P(x)=x+c$ for some real constant $c$.
In the latter case, we get that the polynomial $P(x)+x -(P(a_1)+a_1)$ with degree at most $n$ has at least $m$ distinct roots, namely $a_1,a_2,...,a_m$.
This is also clearly impossible unless it's zero polynomial, i.e. $P(x)=-x+c$ for some real constant $c$.
Hence, we get two possible types of $P$, namely $x+c$ and $-x+c$ where $c$ is a real constant, these are easy to verify.
Yes, for example, $Q(x)=cx^2$ where $c$ be any real constant that $0<c< \min_{i,j\in \{ 1,2,...,m\},i\neq j,a_i+a_j\neq 0} \Big\{ \frac{1}{|a_i+a_j|}\Big\}$.
Or just $Q(x)=1$, which has degree zero.
silouan
04.03.2018 02:18
Borbas wrote: It should be (b) If $n,m\ge 2$ does there exist a polynomial $Q$ with real coefficients and degree exactly $n$ such that: $|Q(a_i)-Q(a_j)|<|a_i-a_j|$ for all $i,j=\{1, 2, ..., m\}$ such that $i<j$
ThE-dArK-lOrD
04.03.2018 07:13
Then just $cx^n$ for suitable $c$?
knm2608
20.04.2018 22:39
Borbas wrote: (b) If $n,m\ge 2$ does there exist a polynomial $Q$ with real coefficients and degree $n$ such that: $|Q(a_i)-Q(a_j)|<|a_i-a_j|$ for all $i,j=\{1, 2, ..., m\}$ such that $i<j$ Edit: See #3 Yes there exist. Consider the following construction $$Q(x)=x^n \;\; \text{and}\;\; |a_i| <\frac{1}{n} \;\; \forall 1\leq i \leq m$$Then we have $$\frac {|Q(a_i)-Q(a_j)|} {|a_i-a_j|} \leq\frac{n}{n^{n-1}}<1$$
aadhitya
16.01.2019 19:20
For part (a), WLOG let $a_1 < a_2 < ....... < a_m$. Therefore the given condition becomes, $|P(i) - P(j)| = a_i - a_j$ if $i > j$. Notice that, $\sum_{i=1}^{m-1} |P(a_{i+1}) - P(a_{i})|$ $ = $ $\sum_{i=1}^{m-1} (a_{i+1} - a_i)$ $=$ $a_m - a_1 = |P(a_n) - P(a_1)|.$ But also we know, $\sum_{i=1}^{m-1} |P(a_{i+1}) - P(a_{i})|$ $\geq$ $| \sum_{i=1}^{m-1} P(a_{i+1}) - P(a_{i}) |$ $=$ $| P(a_m) - P(a_1)|$. Here equality holds if and only if all the terms are of the same sign i.e. $P(a_{i+1}) - P(a_{i}) > 0$ for all $i$ (or) $P(a_{i+1}) - P(a_{i}) < 0$ for all $i$. Now note that, the first case implies, $P(a_i) - P(a_j) = a_i - a_j$ for all $i,j \leq m$ $\implies P(a_i) - a_i = P(a_j) - a_j $ $=$ $c$ (say). SO, $P(x) - (x +c)$ has $m$ roots and $\deg (P(x)) < m$. Therefore $P(x) - (x+c)$ must be zero polynomial. Therefore $P(x) = x + c$. Similarly in the other case we get $P(x) = x - c$. Therefore, the solutions are, $P(x) = x+c$ (or) $P(x) = x - c$ . For part $(b)$ just let $P(x) = cx^n$ where $c$ is an arbitrarily small constant.
user1729
21.07.2019 10:23
Take a look at IMO 2006 P5 for a.
Mathemagician1206
12.03.2024 19:30
For a: another approach spells: WLOG assume$a_1<a_2<a_3...$ Notice that $|P(a_2)-P(a_1)|=|a_2-a_1|$ $\Rightarrow$ $\frac{|P(a_2)-P(a_1)|}{|a_2-a_1|}=1$ This is just the slope of a polynomial $P(x)$ being equated to $1$ for a random constant that is between $a_2$ and $a_1$. Now we make pairs for all such consecutive $a$'s and find that: $|P'(x)|-1=0$ has $m-1$ roots. Therefore at any rate, $P(x)-x+constant$ must have $m$ roots, where $P'(x)$ is the derivative of $P(x)$. Therefore, it must be zero polynomial, by virtue of degree of it. Therefore, upon integrating, we find that $P(x)=x+c$ or $P(x)=-x+c'$, where c is the constant of integration, are the only functions that satisfy this equation.