Polynomial Inequalities

We first let $a$ be the degree of $f(x)$ and $b$ be the degree of $g(x)$ . The given equation tells us that: $a b = 2 a + b$ $b = 2 + \frac{b}{a}$

Since both $a$ and $b$ are positive integers, this means that $\frac{b}{a}$ is an integer, and that $a$ is a factor of $b$ . The last equation also tells us that the difference between $b$ and $\frac{b}{a}$ (which is another factor of $b$ ) is 2, so $b$ cannot be greater than 4. (No integers above 4 are 2 more than one of their factors, as the quotient would be under 2 but above 1.)

This results in two cases: $a = 2$ and $b = 4$ or $a = 3$ and $b = 3$ . Before examining each case, we will make the general statement that $f(x)$ has no constant term. This is evident if we let $s$ be a root of $g(x)$ . (Since the polynomial equality holds on the real line, it holds in the complex plane [according to elementary complex analysis], and the fundamental theorem of algebra [also easily shown from elementary complex analysis] guarantees that $g(x)$ has a root in the complex plane.) At this root, $f(s)^2 g(s) = f(s)^2 (0) = 0$ , so $f(g(s)) = f(0) = 0$ . This prevents $f(x)$ from having a constant term in either case. Now we can examine each case:

• Case I: $a = 2$ and $b = 4$ . In this case, $f(x)$ is a monic quadratic. As mentioned above, it has no constant term, so it may be written $f(x) = x (x - c)$ , for some integer $c$ . This gives: $f(g(x)) = g(x) (g(x) - c)) = (f(x)^2) g(x) = (x (x - c))^2 g(x)$ The analyticity of polynomials allows us to divide through by $g(x)$ (note that the equality must hold for the entire real line and therefore complex plane, so we need not worry about $g(x)$ being zero), and we obtain: $g(x) - c = (x (x - c))^2$ $g(x) = x^4 - c x^3 + c^2 x^2 + c$ The equality and restrictions on $f(x)$ mean that there is only one degree of freedom in finding $g(x)$ . To keep the largest coefficient of $g(x)$ under $10^{100}$ , we must ensure that $c^2 < 10^{100}$ , or that $|c| < 10^{50}$ . This gives us $2 (10^{50} - 1) + 1 = 2 \cdot 10^{50} - 1$ for the number of possible $g(x)$ in this case.

• Case II: $a = 3$ and $b = 3$ . As mentioned above, $f(x)$ cannot have a constant term, so it must be of the form: $f(x) = x (x - c_1) (x - c_2)$ . Note that $c_1 c_2$ and $c_1 + c_2$ must be integers, but $c_1$ and $c_2$ alone need not be (for the moment). Again, we can plug this in: $f(g(x)) = g(x) (g(x) - c_1) (g(x) - c_2)$ $= (f(x)^2) g(x) = ( x(x - c_1)(x - c_2) )^2 g(x)$ Dividing, as we could previously: $(g(x) - c_1)(g(x) - c_2) = ( x(x - c_1)(x - c_2) )^2$ At this juncture, one may use the quadratic formula to find $g(x)$ , but one may circumvent that by noting that both sides are polynomials in $x$ and the right side is a perfect square, so the left side must be one as well. Either way, one arrives at the crucial breakthrough, which is that $g(x)$ is only a valid polynomial when $c_1 = c_2 = c$ : $(g(x) - c)^2 = ( x (x - c)^2) ^2$ Equal squares do not mean equal values; they mean equal or opposite values: $g(x) - c = \pm ( x (x - c)^2 )$ $g(x) = c \pm ( x^3 - 2 c x^2 + c^2 x )$ Again, we find that we only need to set $c^2 < 10^{100}$ to ensure that the magnitudes of $g(x)$ 's coefficients lie strictly under $10^{100}$ . Again, we have $|c| < 10^{50}$ . In this case, however, all values of $c$ yield 2 different solutions for $g(x)$ : one with the plus sign, and one with the minus sign. (Even $c = 0$ results in different solutions.) Thus, instead of $2 \cdot 10^{50} - 1$ solutions, we have twice that, or $2 (2 \cdot 10^{50} - 1) = 4 \cdot 10^{50} - 2$ solutions.

In total, therefore, we have $6 \cdot 10^{50} - 3$ solutions. This number is the difference of $6 \cdot 10^{50}$ , or 6 followed by lots of zeros, and 3. Thus, the difference ends in lots of nines followed by a 7. The last three digits of the number of solutions is $\boxed{997}$ , the correct answer.

If $m$ is the degree of $f$ , and $n$ the degree of $g$ , then $mn = 2m+n$ , so that $(m-1)(n-2) = 2$ . Since $m,n \ge 1$ we deduce that either $m=2,n=4$ , or else $m=n=3$ .

1. If $m=2,n=4$ , then $f(X) = X^2 + aX + b$ , where $g(X)^2 + ag(X) + b \; = \; f(X)^2g(X)$ so $g(X)$ divides $b$ , and hence $b=0$ . Thus we deduce that $g(X) \; = \; f(X)^2 - a \; = \; X^4 + 2aX^3 + a^2X^2 - a$ and we want $|2a|,|a^2|,|-a|$ all to be less than $10^{100}$ . Thus $|a| < 10^{50}$ . There are $2\times10^{50}-1$ polynomials of this type.

2. If $m=n=3$ then $f(X) = x^3 + aX^2 + bX + c$ where $g(X)^3 + ag(X)^2 + bg(X) + c \; = \; f(X)^2g(X)$ so $g(X)$ divides $c$ , and hence $c=0$ , and so $g(X)^2 + ag(X) + b \; = \; f(X)^2$ Comparing coefficients of $X^6$ , we see that either $g(X)$ is monic or $-g(X)$ is monic. Moreover $ag(X) + b \; = \; (f(X) - g(X))(f(X) + g(X))$ If $g(X)$ is monic then $f(X)+g(X)$ has degree $3$ and leading coefficient $2$ , and $ag(X) + b$ is at most cubic. Thus we deduce that $f(X) - g(X)$ is constant, and hence $g(X) = f(X) + d$ for some constant $d$ . Comparing powers of $g(X)$ in the above identity, we deduce that $a=-2d, b=d^2$ , so that $f(X) = X^3 - 2dX^2 + d^2X$ , and hence $g(X) = X^3 - 2dX^2 + d^2X - d$ . Since we want $|-2d|,|d^2|,|-d|$ all to be less than $10^{100}$ , we require $|d| < 10^{50}$ . Thus there are $2\times10^{50}-1$ polynomials $g(X)$ of this type. Similarly, if we assume that $-g(X)$ is monic, then we deduce that $f(X) = X^3 + 2dX^2 + d^2X$ and $g(X) = -X^3 - 2dX^2 - d^2X - d$ for some $|d| < 10^{50}$ , and so we obtain another $2\times10^{50}-1$ polynomials.

Thus there are $N = 6\times10^{50}-3$ polynomials $g(X)$ of the desired type, and the last three digits of $N$ are $997$ .