1

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?

D.R.
  • 8,691
  • 4
  • 22
  • 52

2 Answers2

4

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}.$$

Harry Richman
  • 1,236
-1

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)$.

QED
  • 12,644
  • 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$. –  Dec 14 '17 at 05:34
  • 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. – Erick Wong Dec 14 '17 at 05:35