How many polynomials f ( x ) are there, which satisfy all the following conditions:
Details and assumptions
A polynomial is monic if its leading coefficient is 1. For example, the polynomial x 3 + 3 x − 5 is monic but the polynomial − x 4 + 2 x 3 − 6 is not.
As stated in the problem, the coefficients are real values, not necessarily integer valued.
Clarification: The divisibility condition in 4 is about polynomials, not integer values obtained upon evaluation. For example, x − 1 divides x 2 − 1 . since x 2 − 1 = ( x − 1 ) ( x + 1 ) . x − 2 does not divide x 2 − 1 , even though when " x = 3 ", 1 divides 8.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
All submitted solutions were essentially correct, and all of them shared the same strategy: first find all polynomials satisfying the first four conditions, looking at their roots, and then look at the last condition. The details of the justification varied considerably, though the main ideas were the same. The two featured solutions are a good example of that.
The 2-adic valuation of a rational number, referred to in the last paragraph of the second solution, is the difference between the order of 2 in its numerator and the order of 2 in its denominator. It is a very useful notion in number theory, that serves as a starting point for the theory of p-adic numbers, for the prime number p=2. For more on p-adic numbers see, for example, http://en.wikipedia.org/wiki/P-adic_number
Since f is monic, it determined by its complex roots (including multiplicity). By Property 4, note that if f ( z 0 ) = 0 then either z 0 = 1 or f ( 2 z 0 ) = 0 . We claim that every root of f is either 0 or 2 − n for some nonnegative integer n , for if w is a non-zero root and 2 n w is never equal to 1 then the polynomial f would have the infinite set of roots w , 2 w , 4 w , … .
One solution is given by making all the roots 0 , namely x 1 0 0 0 . For any other solution, define m ≥ 0 to be the largest integer such that f ( 2 − m ) = 0 . Then f has roots 1 , 1 / 2 , 1 / 4 , … , 2 − m , and possibly 0 . We next determine the multiplicities of these roots, so let o ( z ) denote the multiplicity of the root z .
The RHS of Property 4 is divisible by x − 1 but not by ( x − 1 ) 2 , since 2 is not a root of f . Thus o ( 1 ) = 1 , and the RHS of Property 4 is divisible by 2 x − 1 but not by ( 2 x − 1 ) 2 . This implies o ( 1 / 2 ) ≤ 1 , and continuing inductively we see that all non-zero roots must be simple.
Since f has degree 1000, we deduce that f ( x ) = x 9 9 9 − m ( x − 1 ) ( x − 1 / 2 ) ⋯ ( x − 2 − m ) .
It's easy to see that for any m ≤ 9 9 9 , this polynomial satisfies Properties 1, 2, 3, and 4 (property 3 being somewhat unnecessary), but Property 5 places a stricter bound on m .
By considering each factor separately, we see that each factor after the first has odd numerator and denominator a power of 2. The 2-adic valuation of f ( 2 ) is easily seen to be 9 9 9 − m − 1 − 2 − 3 − ⋯ − m = 9 9 9 − m ( m + 3 ) / 2 , and this is non-negative precisely when 0 ≤ m ≤ 4 3 , which gives 44 more solutions in addition to x 1 0 0 0 .
This is a very clearly and carefully written solution. The 2-adic valuation of a rational number, referred to in the last paragraph, is the difference between the order of 2 in its numerator and the order of 2 in its denominator. It is a very useful notion in number theory, that serves as a starting point for the theory of p-adic numbers, for the prime number p=2. For more on p-adic numbers see, for example, http://en.wikipedia.org/wiki/P-adic_number
First, we use the fundamental theorem of algebra with conditions 1 and 2 to write:
f ( x ) = ( x − a 1 ) ( x − a 2 ) . . . ( x − a 1 0 0 0 )
Note that the a i are in complex conjugate pairs, by condition 3.
The important condition is 4. That says that if b is a root of f(x), and b is not 1, then 2b is also a root of f(x) with no smaller multiplicity.
Suppose we have a root c that's not zero or the reciprocal of a power of 2 (includes complex roots). So c, 2c, 4c, etc must all be roots, contradiction (as there are only 1000 at most). Likewise, any root that's a reciprocal of a power of 2 can only appear with multiplicity 1, and there is one smallest such root and all larger such roots appear (including 1 itself).
So any solution with any nonzero root will look like
( x − 1 ) ( x − 2 1 ) . . . ( x − 2 n 1 ) ∗ x 9 9 9 − n
And we calculate that this satisfies condition 5 iff 2 n ( n + 1 ) ≤ 9 9 9 − n , which is satisfied for n at most 43, giving 45 solutions if we include the one with only zero roots.
"Likewise, any root that's a reciprocal of a power of 2 can only appear with multiplicity 1, and there is one smallest such root and all larger such roots appear (including 1 itself)." This is not a completely rigorous justification, but I do not want to be picky, most likely the author could have filled in the details if necessary.
We know f ( x ) has 1000, not necessarily distinct, roots, r 1 , r 2 , . . . , r 1 0 0 0 . Therefore g ( x ) = ( x − 1 ) f ( 2 x ) has the 1001 roots 1 , 2 r 1 , 2 r 2 , . . . , 2 r 1 0 0 0 . For criterion 4 to be met, the 1000 roots of f must all be included in the 1001 roots of g . Clearly, if all the roots of f are 0 , that is, f ( x ) = x 1 0 0 0 , all four criterion are met. If not, then consider the root with the largest absolute value. Note that this root must equal 1 , or else it will not appear in the 1001 roots of g . It follows from there that the remaining roots must be either be 0 or successively lower powers of 2. In other words, our possibilities for f are: f ( x ) = x 1 0 0 0 f ( x ) = x 9 9 9 ( x − 1 ) f ( x ) = x 9 9 8 ( x − 1 ) ( x − 2 1 ) f ( x ) = x 9 9 7 ( x − 1 ) ( x − 2 1 ) ( x − 4 1 ) ⋯ Now, we must also have an integer value of f ( 2 ) . Suppose f has m nonzero roots. Hence, f ( 2 ) = 2 1 0 0 0 − m i = 0 ∏ m − 1 ( 2 − ( 2 1 ) i ) . For this to be an integer, we must have 1 0 0 0 − m ≥ i = 0 ∑ m − 1 i ⟹ m ≤ 4 4 . This gives us 4 5 values for m , and a quick check confirms that they all work, so 4 5 is our final answer.
Note that by comparing degrees and leading coefficients we have the equality ( x − 1 ) f ( 2 x ) = 2 1 0 0 0 ( x − α ) f ( x ) for some real number α . If α = 1 , then f ( 2 x ) = 2 1 0 0 0 f ( x ) and the only way this can happen is if f ( x ) = x 1 0 0 0 . So suppose that α = 1 .
Then x − 1 is a factor of f ( x ) , so f ( x ) = ( x − 1 ) f 1 ( x ) , and f ( 2 x ) = ( 2 x − 1 ) f 1 ( 2 x ) , implying that 2 x − 1 (or equivalently x − 2 1 ) is a factor of ( x − α ) f ( x ) . Again, either α = 2 1 or x − 2 1 is a factor of f ( x ) .
We repeat this process of extracting a factor of f ( x ) and then obtaining a new factor on the left hand side. of the polynomial equation in the first line above. We see that among the roots of f ( x ) are 1 , 2 1 , 4 1 , … 2 1 − r and that α = 2 − r for some integer r ≥ 1 . The polynomial equation transforms as follows:
( x − 1 ) ( 2 x − 1 ) ( 2 x − 2 1 ) ⋯ ( 2 x − 2 − r ) g ( 2 x ) = 2 1 0 0 0 ( x − 1 ) ( x − 2 1 ) ⋯ ( x − 2 − r ) ( x − α ) g ( x ) for some polynomial g ( x ) . All the linear terms cancel, and we are left with an extra factor of 2 r + 1 on the left hand side. Dividing by this gives us g ( 2 x ) = 2 9 9 9 − r g ( x ) with the unique monic solution g ( x ) = x 9 9 9 − r . This means that f ( x ) = x 9 9 9 − r ( x − 1 ) ( x − 2 1 ) ⋯ ( x − 2 r ) .
Lastly we check for which values of r is f ( 2 ) an integer. The first factor contributes 2^{999-r . After that there are factors of 2 only in the denominator, 2 − 2 − k contributing a factor of 2 − k . Hence we need 9 9 9 − r ≥ 1 + 2 + ⋯ + r = 2 r ( r + 1 ) which happens (for non-negative r ) when r ≤ 4 3 . So the valid solutions occur when r = 0 , 1 , ⋯ , 4 3 and adding the one at the start where α = 1 , gives a total of 4 5 solutions.
One may fret at the fact that there are 5 conditions, however, we can "group" the conditions. We will look at the first 4 first, since they contain the variable x , determine the set of functions, and evaluate using condition 5 to see how many satisfy all the conditions.
Now let us rewrite the 4th condition as follow:
f ( 2 x ) ( x − 1 ) = f ( x ) × k (*)
where k is a certain expression. In this form, we can easily notice that it is neat to consider the roots of f ( x ) . Because, if r is a root of f ( x ) that = 1 , then we must have that 2 x is also a root of f ( x ) . By induction, it is clear that 2 m x is also a root for an integer m .
It necessarily follows that f ( x ) does not have any complex roots . For instance, we can always double them to get an infinite number of roots, which violates the conditions. In addition, we also have that all roots are either 0 , 1 , or of the form ( 2 1 ) k or else, f ( x ) would have an infinite number of roots since we can always double and get new roots, until we get 1 after a certain doubling.
Whence, we can express f ( x ) in the following form:
f ( x ) = x p 0 ( x − 1 ) p 1 ( x − 2 1 ) p 2 ( x − 1 / 4 ) p 3 … ( x − ( 2 1 ) r − 1 ) p r
where positive integers p 0 , … , p r satisfy p 0 p 1 … p r = 1 0 0 0 So subbing this into (*), we get:
2 p 0 x p 0 ( 2 x − 1 ) p 1 ( 2 x − 2 1 ) p 2 … ( 2 x − ( 2 1 ) r − 1 ) p r ( x − 1 ) = x p 0 ( x − 1 ) p 1 ( x − 2 1 ) p 2 ( x − 4 1 ) p 3 … ( x − ( 2 1 ) r − 1 ) p r × k
Now, we see lots of multiples of 2 , it would be intuitive to pull out all the multiples of 2 to derive the following:
2 1 0 0 0 x p 0 ( x − 2 1 ) p 1 ( x − 1 / 4 ) p 2 … ( x − ( 2 1 ) r ) p r ( x − 1 ) = x p 0 ( x − 1 ) p 1 ( x − 2 1 ) p 2 ( x − 4 1 ) p 3 … ( x − ( 2 1 ) r − 1 ) p r × k
Now, we can see that by matching coefficients we can set k = 2 1 0 0 0 x + 2 1 r × 2 1 0 0 0 , a linear equation in x . After a simple transformation, we can also easily get p 1 = p 2 = … = p r = 1 . So f(x) is of the form:
f ( x ) = x 1 0 0 0 − r ( x − 1 ) ( x − 2 1 ) ( x − 4 1 ) … ( x − ( 2 1 ) r − 1 )
where 0 ≤ r ≤ 1 0 0 0 .
Now, we have to work on the final 5th condition, the interested reader can verify that when r = 4 5 , f ( 2 ) is not an integer. In fact, try r = 4 6 , 4 7 , 4 8 will motivate us to conjecture that the last condition holds only for r ≤ 4 4 . Let us rewrite the expression for f ( 2 ) as follows:
f ( 2 ) = 2 1 0 0 0 − r ( 2 − 1 ) ( 2 − 2 1 ) … ( 2 − ( 2 1 ) r − 1 ) = 2 1 0 0 0 ( 1 − 2 1 ) ( 1 − 4 1 ) ( 1 − 8 1 ) … ( 1 − ( 2 1 ) r ) = 2 1 0 0 0 ( 2 1 ) ( 4 3 ) ( 8 7 ) … ( 2 r 2 r − 1 )
since the exponent of 2 in the denominator of the product cannot exceed that of 1 0 0 0 , we need only solve 2 r ( r + 1 ) ≤ 1 0 0 0 , which gives r ≤ 4 4 . It is routine to verify that r = 0 , 1 work, giving a total of 45 solutions.
SInce this polynom has 1 0 0 0 roots, we can written it as :
P ( x ) = ( x − a 1 ) ( x − a 2 ) … ( x − a 1 0 0 0 ) , so this satisfy that P ( x ) is monic and also has degree 1 0 0 0 . And WLOG that ∣ x 1 ∣ ≤ ∣ x 2 ∣ ≤ ∣ x 3 ∣ … ∣ x 1 0 0 0 ∣
Now, we see that : P ( x ) ∣ ( x − 1 ) P ( 2 x ) ∏ i = 1 1 0 0 0 ( x − x i ) ∣ ( x − 1 ) ∏ i = 1 1 0 0 0 ( 2 x − x i ) implies ∏ i = 1 1 0 0 0 ( x − x i ) ∣ 2 1 0 0 0 . ( x − 1 ) ∏ i = 1 1 0 0 0 ( x − 2 x i ) .
So, we see that, on LHS there are 1 0 0 0 roots, but in RHS there are 1 0 0 1 roots. So, Between LHS and RHS should be share 1 0 0 0 roots. We will divide it into two case :
Case 1 : ( x − 1 ) ∤ P ( x ) . So, In RHS and LHS should be has the same roots. But, ∣ 2 a 1 ∣ ≤ ∣ a 1 ∣ ≤ ∣ a 2 ∣ … ≤ ∣ a 1 0 0 0 ∣ . So, it should be x 1 = x 2 = … = x 1 0 0 0 = 0 . So, P ( x ) = x 1 0 0 0
Case 2 : ( x − 1 ) ∣ P ( x ) . So, we can write it as ∏ i = 1 9 9 9 ( x − x i ) ∣ 2 1 0 0 0 . ( x − 2 1 ) ∏ i = 1 9 9 9 ( x − 2 x i ) . And, see that pattern, ∏ i = 1 1 0 0 0 − k ( x − x i ) ∣ 2 1 0 0 0 . ( x − 2 k 1 ) ∏ i = 1 1 0 0 0 − k ( x − 2 x i
By (4) there exists a polynomial P ( x ) such that f ( x ) ⋅ P ( x ) = ( x − 1 ) ⋅ f ( 2 x ) … ( ∗ 1 ) , since f is monic and has degree 1000, P is linear and his leading coefficient is 2 1 0 0 0 . Let n be the greatest integer such that x n divides f ( x ) (note that n can be 0) then we can write f ( x ) = x n ⋅ g ( x ) , where g is monic and g ( 0 ) = 0 . Replacing in ( ∗ 1 ) we get: x n ⋅ g ( x ) ⋅ P ( x ) = ( x − 1 ) ⋅ 2 n ⋅ x n ⋅ g ( 2 x ) then g ( x ) ⋅ P ( x ) = 2 n ⋅ ( x − 1 ) ⋅ g ( 2 x ) … ( ∗ 2 ) Put x = 0 in the last equation, since g ( 0 ) = 0 , we have P ( 0 ) = − 2 n . So P ( x ) = 2 1 0 0 0 x − 2 n , and replacing this in ( ∗ 2 ) we get: g ( x ) ⋅ ( 2 1 0 0 0 − n x − 1 ) = ( x − 1 ) ⋅ g ( 2 x ) … ( ∗ 3 ) For n = 1 0 0 0 we get f ( x ) = x 1 0 0 0 which of course is a solution.
Consider now n ≤ 9 9 9 . If g ( r ) = 0 and r = 2 n − 9 9 9 then by ( ∗ 3 ) we get g ( r / 2 ) = 0 ; in other words: if r is a root of g and r = 2 n − 9 9 9 then r / 2 is also a root of g .
Putting x = 1 in ( ∗ 3 ) we get g ( 1 ) = 0 , so 1 is a root of g and using the result of the previous paragraph we get that the 1 0 0 0 − n following numbers: 1 , 2 − 1 , 2 − 2 , … , 2 − ( 9 9 9 − n ) are roots of g , but g has degree 1 0 0 0 − n and is monic, so: g ( x ) = ( x − 1 ) ( x − 2 − 1 ) ⋯ ( x − 2 − ( 9 9 9 − n ) ) and then f ( x ) = x n ⋅ ( x − 1 ) ( x − 2 − 1 ) ⋯ ( x − 2 − ( 9 9 9 − n ) ) , and it is clear that this polynomial satisfies properties (1) to (4).
Finally, note that we can write f ( 2 ) = 2 0 ⋅ 2 1 ⋅ 2 2 ⋯ 2 9 9 9 − n 2 n ⋅ k , where k is a odd integer, so f ( 2 ) is integer if and only n ≥ 0 + 1 + 2 + ⋯ + ( 9 9 9 − n ) , and solving this inequality we obtain 9 5 6 ≤ n ≤ 9 9 9 . So, for each such n we get one polynomial.
Taking in account f ( x ) = x 1 0 0 0 , we conclude that the answer is 9 9 9 − 9 5 5 + 1 = 4 5 .