There was an MIT PRIMES application problem that goes like this: (don't worry, the admission ended on Dec 1, so I'm not cheating or anything)

For all $d\geq 0$, determine if there is a polynomial $p(x)$ with degree $d$ such that for all $n$ in $1\ldots 99$ inclusive satisfies $$p(n)=n+\frac1n$$ and if so, what is $p(x)$ and find the value of $p(100)$.

In English terms: find a polynomial with degree $d$ such that $$p(1)=1+\frac11=2$$ $$p(2)=2+\frac12=2.5$$ and so on. What values of $d$ work? What are the polynomials for each of those $d$? What is $p(100)$ for each of those polynomials?

My solution was to brute force it by solving a matrix (see Finding polynomials from huge sets of points), but Java wasn't good enough to do all that math (couldn't contain huge numbers with good enough precision).

Is there a better, more elegant way to do the problem? If not, how would I brute force it?


If $p(x)$ satisfies the given conditions, then $$ f(x) = xp(x)-x^2-1 $$ is a polynomial of degree $d+1$ (assuming $d\geq 1$) with zeros at $x = 1,2,\ldots,99$.

Note that $f$ satisfies $f(0) = -1$, so it cannot be the polynomial that is identically zero-valued. Thus $f$ can have at most $d+1$ distinct zeros, so we must have $d\geq 98$.

If $d = 98$, then the location of zeros of $f(x)$ implies $$f(x) = k(x-1)(x-2)\cdots(x-99)$$ for some constant $k$. But since $$ -1 = f(0) = k\cdot(-1)^{99}(99!),$$ we may solve for $k = \frac1{99!}$. In this case $f(100) = k\cdot(99!) = 1$, so then $$p(100) = \frac1{100} (f(100) + 100^2 + 1) = 100 + \frac2{100}.$$

If $d\geq 99$, then we have $$f(x) = \frac1{99!}(x-1)(x-2)\cdots(x-99)g(x)$$ for some (arbitrary) polynomial $g(x)$ of degree $d - 98$, normalized to $g(0) = 1$. In this case $f(100) = g(100)$, and $$ p(100) = \frac1{100} (g(100) + 100^2 + 1 ) = 100 + \frac{1 + g(100)}{100}.$$


From the given condition $nP(n)=n^2+1$ for $n=1,2,\cdots,99$. So the polynomial $P^{\star}(x)=xP(x)-x^2-1$ of degree $d+1$, has 99 zeros. If $d<98$ then $P^{\star}(x)$, despite of being of degree $d+1$, would have $>d+1$ roots, and hence should be identically equal to zero for every $x$. Then $P(100)$ would be simply $\frac{P^{\star}(100)+(100^2+1)}{100}=100+\frac1{100}$.

Now if $d=98$ then we can represent $$P^{\star}(x)=(x-1)(x-2)\cdots(x-99)$$ assuming $P$ to be a monic polynomial. Then $P(100)=\frac{P^{\star}(100)+(100^2+1)}{100}=\frac{99!+10001}{100}$.

If $d>98$ then we can represent $$P^{\star}(x)=(x-1)(x-2)\cdots(x-99)g(x)$$ With $g(x)$ being a polynomial of degree $\ge1$. But then due to indeterminacy of $g(x)$ we can't calculate the exact value of $P(100)$.

  • $\begingroup$ That's wrong: $P^{\star}(x)=xP(x)-x^2-1$ doesn't only have to have zeros at $x=1,2,\ldots,99$, it also must satisfy $P^{\star}(0)=0\cdot P(0)-0^2-1=-1$. $\endgroup$ – Professor Vector Dec 14 '17 at 5:34
  • $\begingroup$ You can’t assume $P^*$ is monic, since it necessarily has constant term equal to $-1$. Similarly, the hypothetical case where $P^*$ is identically zero cannot actually occur. $\endgroup$ – Erick Wong Dec 14 '17 at 5:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.