Polinomios Buenos

[Emerson Soriano]

Un polinomio $P(x)$ es llamado bueno si cumple con las siguientes dos condiciones:

• $P(x)=0$ o el grado de $P(x)$ es menor o igual que $5$.

• $P(x)$ tiene coeficientes enteros.

Halle cuántos polinomios buenos $P(x)$ satisfacen la desigualdad $0\leq P(r)<120$, para todo $r=0$, $1$, $2$, $3$, $4$, $5$.

[jhn]

Spoiler: mostrar

Dados enteros $a_0, a_1,\ldots, a_5\in\{0,1,2,\ldots,119\}$ sea $P_k$ el polinomio de grado $\le k$ tal que $P_k(i)=a_i$ para $i=0,\ldots, k$. Por ejemplo $P_0(x)=a_0$ y $P_1(x)=a_0+(a_1-a_0)x$. Hay $120^{k+1}$ polinomios $P_k$, pero a partir de $k=2$ algunos coeficientes podrían ser racionales no enteros. Ahora bien, $P_2(x)-P_1(x)$ se anula en 0 y 1, luego $P_2(x)-P_1(x)=mx(x-1)$ y $P_2(x)\in Z[x]$ si y sólo si $m\in Z$; evaluando en $x=2$ resulta $P_2(2)-P_1(2)=2m$, es decir que $a_2=P_1(2)+2m$ debe tener la misma paridad que $P_1(2)$. Y recíprocamente, si $a_2\equiv P_1(2)\pmod{2}$ entonces $P_2(x)\in Z[x]$. Esto significa que, una vez elegidos $a_0$ y $a_1$ de alguna de las $120^2$ maneras posibles, $a_2$ se puede elegir de $120/2=60$ maneras. Análogamente, $P_3(x)-P_2(x)=mx(x-1)(x-2)$ y $P_3(x)\in Z[x]$ si y sólo si $m\in Z$ y $P_3(3)-P_2(2)=6m$, es decir si $a_3\equiv P_2(3)\pmod{6}$. O sea que elegidos $a_0$, $a_1$ y $a_2$ de alguna de las $120^2\cdot 60$ maneras posibles, $a_3$ se puede elegir de $120/6=20$ maneras. Siguiendo de este modo $a_3$ se puede elegir de $120/24=5$ maneras y $a_5$ de una manera. Luego la respuesta es $120^2\cdot 60\cdot 20\cdot 5\cdot 1=86400000$.