Let $S$ be a set of integers with the property that any integer root of any non-zero polynomial with coefficients in $S$ also belongs to $S$. If $0$ and $1000$ are elements of $S$, prove that $-2$ is also an element of $S$.
Problem
Source: Pan African Maths Olympiad
Tags: algebra, polynomial
tomkern
11.08.2005 20:57
There might be a simpler soln, but this does work: $1000x + 1000 = 0 \leadsto -1 \in S$ $-x^{1000}-x^{999}-x^{998}-x^{997} ... -x^2-x+1000 = 0 \leadsto 1 \in S$ $-x^{10}+x^4-x^3+1000 = 0 \leadsto -2 \in S$
Singular
11.08.2005 22:24
Consider 1000x + 1000. so -1 is in S Consider $(x+2)(-x^9 + 2x^8 - 4x^7 + 8x^6 -16x^5 +31x^4 -63x^3 +125x^2 -250x + 500)$ which can be checked to have coefficents in $\{ 0, -1, 1000 \}$ when expanded. Result follows.
Magnara
11.08.2005 23:59
As shown above, we have -1 and 1 in S. Then, by x+1000=0, we have -1000 in S. Then, by finding the binary expansion of 1000, which is 1111101000, we know that 2 is a root to x^9+x^8+x^7+x^6+x^5+x^3-1000=0. I know it's not the simplest solution, but it's very intuitive.
warut_suk
08.10.2005 14:40
Magnara wrote: As shown above, we have -1 and 1 in S. Then, by x+1000=0, we have -1000 in S. Then, by finding the binary expansion of 1000, which is 1111101000, we know that 2 is a root to x^9+x^8+x^7+x^6+x^5+x^3-1000=0. But it asks for $-2$...
seasonal squirrel
22.10.2009 03:29
I just wanted to post a simpler solution
As proven earlier $ 1, 10$ $ \in S$
So therefore the polynomial $ x^{3} + x + 10$ satisfies the hypothesis of the problem.
Finally checking $ x = - 2$ we see that this satisfies the polynomial and hence $ -2 \in S$ ,as desired