How many polynomials?

If $f(x)$ has a degree of zero, then since it is monic, we must have $f(x)=1$ , which yields the equation $0=n$ , contradiction to the positive nature of $n$ , so $f(x)$ must have positive degree.

Assuming that $f(x)$ has positive degree, note we can rewrite this equation as $xf(x+a) = (x+n)f(x)$ . Clearly, then we must have $x|(x+n)f(x) \implies x|f(x) \implies f(x) = xf_1(x)$ for some monic polynomial $f_1(x)$ , resulting in the equation $xf(x+a) = x(x+a)f_1(x+a) = x(x+n)f_1(x)$ If $f_1(x)=1$ , then the equation is clearly satisfied if $n=a$ , and thus $f(x) = x(x+n)$ , which satisfies all conditions. Otherwise, assume $f_1(x)$ has positive degree.

Clearly, then, we have that $a$ cannot equal $n$ , otherwise we have $x(x+n)f_1(x+n) = x(x+n)f_1(x) \implies f_1(x+n) = f_1(x)$ which cannot happen, since $n>0$ . Thus we have from the previous equation that $x+a | x(x+n)f_1(x) \implies (x+a) | f_1(x)\implies f_1(x) = (x+a)f_2(x)$ for some monic polynomial $f_2(x)$ . With similar logic as above, if $f_2(x)$ is constant, then substituting yields $a=\dfrac{n}{2}$ and $f(x) = x(x+a)(x+2a)$ .

The process can clearly therefore be generalized until factorization terminates. One can see that one can create the chain of factorizations $f_1 = (x+a)f_2(x),\:f_2(x) = (x+2a)f_3(x), \: \ldots,\:$ until we have for some $k$ that $f_k(x) = (x+ka)(1)$ , as the factorizations must terminate due to $f(x)$ having finite degree.

Therefore, it can be seen that for some nonnegative integer $k$ , that $f(x) = \displaystyle\prod_{i=0}^{k}(x+ia)$ Substituting this into the original equation yields $xf(x+a)=x(x+a)(x+2a)\cdots(x+(k+1)a) = (x+n)(x)(x+a) \cdots (x+ka)$ and simplifying yields $x+(k+1)a = x+n \implies a =\dfrac{n}{k+1}$

Thus, $a$ is a rational root of $f(x)$ . However, since $f(x)$ is a monic polynomial with integer coefficients, by the Rational Root Theorem we must have that $a$ is an integer, so $k+1 | n$ . There are thus $d(n)$ positive values of $k+1$ , and so $d(n)$ nonnegative values of $k$ and consequently $d(n)$ different possible $f(x)$ for $n$ .

Thus it suffices to maximize $d(n)$ for $1 \leq n < 1000$ . Note that since $2*3*5*7*11 = 2310 > 1000$ , $n$ can have no more than $4$ distinct prime divisors. Since $d(n)$ relies only on the exponents of the prime divisors, to maximize the exponents it suffices to use the smallest primes, and so we must have that $n = 2^a3^b5^c7^d$ for nonnegative $a, b, c, d$ .

If $n$ has only two prime divisors, by the same logic, let $n=2^a3^b$ for positive $a, b$ . Clearly $b <6$ , and so merely testing for the possible values of $b$ and then finding the maximum possible value of $a$ such that $n<1000$ yields that the maximum for this case is $d(n)=24$ for $n=2^5\cdot 3^3$ .

If $n$ has only three prime divisors, then let $n=2^a3^b5^c$ for positive $a, b, c$ . Since $c<4$ , using a similar method to before, we find that the maximum for this case is when $d(n)=30$ for $n=2^4\cdot 3^2 \cdot 5^1$ .

If $n$ has four prime divisors, then let $n=2^a3^b5^c7^d$ for positive $a, b, c, d$ . Since $a, b, c \geq 1$ , we must have that $d \leq 1 \implies d=1$ , so $2^a3^b5^c < \dfrac{1000}{7} \approx 143$ . Since also $a, b \geq 1$ , we have $2^13^15^c \leq 2^a3^b5^c < 143 \implies 5^c < \dfrac{143}{6} < 25 \implies c=1$ . Then we have $2^a3^b < \dfrac{1000}{5\cdot 7} \approx 29$ . Using casework one can see that the maximum is achieved for when $a=3, b=1$ , so we have that maximum of $d(n)$ is $4\cdot 2 \cdot 2 \cdot 2=32$ for $n=2^33^15^17^1$ .

Since the maximum of all three cases is $32$ , the desired maximum number of polynomials for $n<1000$ is thus $\boxed{32}$ .

We claim that if we fix $n$ , all that satisfy the functional equation are of the form $f(x)=x(x+d)(x+2d)...(x+n)$ , where $d$ is a divisor of $n$ .

Note that if we let $x=r$ , where $r$ is a root of $f(x)$ , then either $r=0$ , or $r+a$ is a root of $f(x$ . Thus, since $f(x)$ has only finitely many roots, all the roots of $f(x)$ are of the form $-ka$ , for some nonnegative integer $k$ .

Now, rearrange the functional equation to $xf(x+a)=(x+n)f(x)$ . Letting $x=-n$ , we find that $-(n-a)$ is a root of $f(x)$ , so for some positive integer $k$ , $-n=-ka$ , so $a$ is a positive integer divisor of $n$ . Further, we know that if we consider the multiset $S$ , of the roots of $f(x)$ , then shifting all the elements of $S$ by $-a$ and adding $0$ is equivalent to adding $-n$ to $S$ . Hence, it follows that $S=\{0,-a,-2a,...,-(n-a)\}$ . Thus, the number of polynomials that satisfy the functional equation for fixed $n$ is the number of divisors of $n$ .

Now, we want to maximize the number of divisors, $\sigma(n)$ over $n<1000$ . Let $k$ be the value of $n$ such that $\sigma(n)$ is maximized and $k$ is minimal. Then, if we write $k=2^{e_1}3^{e_2}5^{e_3}...$ , we must have $e_1 \geq e_2 \geq...$ . Thus, as $2*3*5*7*11>1000$ , the only prime factors of $k$ are $2$ , $3$ , $5$ , and $7$ . From here, with a little casework, we find that $k=2^3*3*5*7$ and the answer is $32$ .