A polynomial $P(x)$ with integer coefficients satisfies the following: $P(5) = 25, P(7) = 49, P(9) = 81$. How do I find the minimal possible value of $|P(10)|$?
Asked
Active
Viewed 1,592 times
3
-
This might be a parabola of degree 2. You can find the y coordinate of the vertex very easily: $y_0=\frac{D}{4a}$ – PinkyWay Dec 02 '19 at 23:58
2 Answers
3
We can write $p(x)=q(x)(x-5)(x-7)(x-9)+x^2$.
Now $p(10)=q(10)(10-5)(10-7)(10-9)+100=q(10) \cdot 5 \cdot 3 \cdot 1 +100=15 \cdot q(10)+100$
So we want $q(10)$ to be "as close as possible" to $-\frac{100}{15}=-6,67\dots$, i.e., we want $q(10)=-7$ and then $$|p(10)|=|-15 \cdot 7 +100|=|-105+100|=5.$$ So for example take $q(x)=x-17$ and then we get the minimal value for $|p(10)|=5$.
EDIT: unicity of form for representing $p(x)$
Suppose $g(x) \neq x^2$ such that $g(5)=25, g(7)=49, g(9)=81$. Then $g(x)-x^2$ has at least three roots, namely $5,7,9$ so $g(x)-x^2=r(x)(x-5)(x-7)(x-9)$ or in other words $g(x)=r(x)(x-5)(x-7)(x-9)+x^2$. Now we have two different representations for $p(x)$, i.e. $p(x)=q(x)(x-5)(x-7)(x-9)+x^2$ and $p(x)=h(x)(x-5)(x-7)(x-9)+g(x)$ , but we can substitute $g(x)=r(x)(x-5)(x-7)(x-9)+x^2$ inside the first representation for $p(x)$ and get $$p(x)=h(x)(x-5)(x-7)(x-9)+r(x)(x-5)(x-7)(x-9)+x^2=\\=[h(x)+r(x)](x-5)(x-7)(x-9)+x^2=q(x)(x-5)(x-7)(x-9)+x^2$$ where $q(x)=r(x)+h(x)$. So we can assume WLOG the representation $p(x)=q(x)(x-5)(x-7)(x-9)+x^2$.
user26857
- 52,094
user289143
- 4,440
-
I like this one, nice and easy. But how do we know there's no other polynomial with the same values for given points, which has even smaller value at 10? – Nik Dec 03 '19 at 04:21
-
It's all there, Nik. $p(10)=15q(10)+100$, $q$ has integer coefficients, $q(10)$ is an integer, $15q(10)+100=5(3q(10)+20)$ is an integer multiple of $5$, QED. – Gerry Myerson Dec 03 '19 at 04:48
-
This all holds for a representation we chose, where p(x) = q(x)(x - 5)(x - 7)(x - 9) + x^2 (sorry for the formula style, writing from the phone). What is not obvious to me is how to prove this is the only possible form for our polynomial. – Nik Dec 03 '19 at 06:09
-
$p(x)-x^2=0$ for $x=5,7,9$, Nik, so $p(x)-x^2=(x-5)(x-7)(x-9)q(x)$ for some polynomial $q(x)$. – Gerry Myerson Dec 04 '19 at 21:28
-
Thank you for your answers, Gerry! But there's no strict prove that this is the only possible polynomial. P(x) - x^2 is one but might not be the only one polynomial that has 0 values at given points. – Nik Dec 08 '19 at 06:07
-
If $f(x)$ is a polynomial vanishing at $a,b,c$ then $f(x)$ is a polynomial multiple of $(x-a)(x-b)(x-c)$. Are you not familiar with this fact? Let's do it one step at a time. The Division Theorem says when you divide $f(x)$ by $x-a$ you get a remainder of degree zero, that is, a constant, $r$. So $f(x)=(x-a)p(x)+r$. Let $x=a$, then $f(a)=r$, so $f(x)=(x-a)p(x)+f(a)$. Now if $f(a)=0$ this says $f(x)=(x-a)p(x)$. If also $f(b)=0$ for some $b\ne a$, then $(b-a)p(b)=0$, so $p(b)=0$, so $p(x)=(x-b)s(x)$ for some polynomial $s(x)$, so $f(x)=(x-a)(x-b)s(x)$. One more step, and we're done! OK? – Gerry Myerson Dec 09 '19 at 02:57
-
@GerryMyerson What I mean is not only $$x^2$$ may have given values at given points. Surely its the most obvious one, but there's no prove its the only one possible. – Nik Dec 09 '19 at 15:20
-
So there might be some $g(x)$, where $g(5) = 25$, $g(7) = 49$, $g(9) = 81$ and yet $g(x) \neq x^2$ – Nik Dec 09 '19 at 15:28
-
Let me clarify this a bit more. The initial solution was basically to represent $p(x) = q(x) + g(x)$, where $q(x) = 0$, for $x = 5, 7, 9$, and $g(5) = 25$, $g(7) = 49$, $g(9) = 81$ This representation is valid for sure, but then $g(x)$ was chosen to be $x^2$. The missing part here is: how to prove this is the only possible $g(x)$. – Nik Dec 09 '19 at 15:50
-
1
-
What I have proved, Nik, is that if $g(5)=25$ and $g(7)=49$ and $g(9)=81$ then $g(x)=x^2+(x-5)(x-7)(x-9)r(x)$ for some polynomial $r(x)$. So, yes, there are polynomials other than $x^2$, but they are all of the form $x^2+(x-5)(x-7)(x-9)r(x)$. For every single polynomial $g(x)$ that takes on those values, you can find a polynomial $r(x)$ such that $g(x)=x^2+(x-5)(x-7)(x-9)r(x)$. – Gerry Myerson Dec 09 '19 at 20:50
3
Here's the theory (prove it!) behind the problem:
For a polynomial $P(x)$ with integer coefficients, if $ a_i, a_j \in \mathbb{N}$, then $ a_i-a_j \mid P(a_i) - P(a_j)$.
Given (finitely many) values $a_i , b_i$ such that $a_i - a_j \mid b_i - b_j$ hold over all pairs, then there exists a polynomial $P(x)$ with integer coefficients such that $P(a_i) = b_i$ if and only if the interpolating polynomial has integer coefficients.
So $10 - 5 \mid P(10) - 25$, $10-7 \mid P(10) - 49$, $10-9 \mid P(10) - 81$.
So we require $ P(10) \equiv 0 \pmod{5}, P(10) \equiv 1 \pmod{3}$.
This gives $P(10) \equiv 10 \pmod{15}$.
Hence, the minimum possible value of $|P(10)| = |-5| = 5$.
Thankfully, the interpolating polynomial has integer coefficients (check it), so this is truly the minimum.
Proof:
First claim: $ a_i^n - a_j^n = (a_i-a_j) (a_i^{n-1}+a_i^{n-2}a_j+\ldots+a_j^{n-1})$.
So $(a_i - a_j)$ is a factor of $\sum p_k (a_i ^k - a_j ^k)$.
Second claim:
Given $2n$ values that satisfy the conditions, let the interpolating polynomial be $I(x)$.
If the interpolating polynomial has non-integer coefficients,
let $P(x) = Q(x) \prod(x-a_i) + I(x)$ with $\deg(P) \geq n, \deg(I) \leq n-1$.
Let $k$ be the largest degree of $Q(x)$ that has a non-integer coefficient, then the coefficient of $x^{k+n}$ will be a non-integer, so no polynomial with integer coefficients exist.
Conversely,if the interpolating polynomial has integer coefficients, we are done.
Calvin Lin
- 68,864
-
Very nice. Can you make this constructive, that is, use this argument to find $P$ satisfying the hypotheses and having $|P(10)|=5$? – Gerry Myerson Dec 03 '19 at 00:54
-
@gerry I deleted an erroneous comment. I am now not certain that such a polynomial must exist. Will think about it. – Calvin Lin Dec 03 '19 at 03:03
-
The other answer constructs an example, Calvin, so it does exist. – Gerry Myerson Dec 03 '19 at 04:50
-
@GerryMyerson Yes, and I indicated as such in the solution. I've now edited in the actual version of the theory. Interestingly, there are cases where the condition holds, but the resultant polynomial cannot be an integer (which makes for a fun problem). – Calvin Lin Dec 03 '19 at 08:07
-
In terms of the example, Calvin, is $I(x)$ meant to interpolate just $P(5)=25$, $P(7)=49$, and $P(9)=81$? or is it meant to also satisfy $P(10)=-5$? – Gerry Myerson Dec 03 '19 at 08:47
-