Maths Olympiad Prep

Library / /191 of 299

Algebra Difficulty 6.8 National Olympiad Prove it Iran

Find all injective functions f:Z0Z0f : \mathbb{Z}^{\ge 0} \rightarrow \mathbb{Z}^{\ge 0} such that for all nNn \in \mathbb{N} and every (n+1)(n+1)-tuple of real numbers like (a0,,an)(a_0, \dots, a_n) where not all of them are equal to zero, the polynomial i=0naixi\sum_{i=0}^{n} a_i x^i has a real root if and only if the polynomial i=0naixf(i)\sum_{i=0}^{n} a_i x^{f(i)} has a real root.

Solution

As P(x)=1P(x) = 1 has no real root, xf(0)x^{f(0)} has also no real root. So f(0)=0f(0) = 0.
Now considering xi+1x^i + 1, it has a real root if and only if ii is odd. So ii and f(i)f(i) have the same parity.
For even nn consider the following polynomial in which a,ϵa, \epsilon are positive numbers:
P(x)=xn+nan1x+(n1)an+ϵ P(x) = x^n + n a^{n-1} x + (n-1) a^n + \epsilon
This polynomial has no real root, indeed applying AM-GM inequality yielding
xn+an++annxan1x. x^n + a^n + \cdots + a^n \ge n x a^{n-1} |x|.
Then by the problem's condition, the polynomial
Q(x)=xf(n)+nan1xf(1)+(n1)an+ϵ Q(x) = x^{f(n)} + n a^{n-1} x^{f(1)} + (n-1) a^n + \epsilon
has no real root. Thus q(a1f(1))q(-a^{\frac{1}{f(1)}}) should be positive yielding:
af(n)f(1)+ϵ>an    af(n)f(1)an a^{\frac{f(n)}{f(1)}} + \epsilon > a^n \implies a^{\frac{f(n)}{f(1)}} \ge a^n
By putting aa greater and less than 1 we get f(n)=nf(1)f(n) = n f(1).
For odd nn consider the polynomial (xn+a)2+ϵ(x^n + a)^2 + \epsilon for a positive aa and ϵ\epsilon. This polynomial is obviously positive so
x2nf(1)+2axf(n)+a2+ϵ>0 x^{2n f(1)} + 2a x^{f(n)} + a^2 + \epsilon > 0
By putting x=a1f(n)x = -a^{\frac{1}{f(n)}} we have:
a2nf(1)f(n)+a2+ϵ>2a2    a2nf(1)f(n)a2    f(n)=nf(1). a^{\frac{2n f(1)}{f(n)}} + a^2 + \epsilon > 2a^2 \implies a^{\frac{2n f(1)}{f(n)}} \ge a^2 \implies f(n) = n f(1).
This finishes our proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.