Problemas IMO con polinomios: taxonomía y resolución

Taxonomía de problemas olímpicos con polinomios

Los problemas de competencia que involucran polinomios se pueden clasificar en cinco categorías principales. Reconocer la categoría es el primer paso para elegir la técnica correcta.

Categoría 1: Divisibilidad. "$f(n) \mid g(n)$ para todo $n\in\mathbb{Z}$", o "$p(a)\mid q(b)$ para $a,b$ relacionados". Técnicas: identidades algebraicas, propiedades de $\mathbb{Z}[x]$, la propiedad $(a-b)\mid f(a)-f(b)$, factorización via ciclotómicos.

Categoría 2: Valores en enteros. "Encontrar todos los enteros $n$ tales que $f(n)$ es cuadrado perfecto / primo / entero". Técnicas: cotas, reducción módulo un entero fijo, desigualdades entre raíces consecutivas.

Categoría 3: Identidades funcionales polinomiales. "$P(P(x)) = P(x)$", "$P(x^2) = P(x)^2 + c$", etc. Técnicas: análisis de raíces del iterado, comparación de grados, substitución de las raíces de uno en el otro.

Categoría 4: Existencia y unicidad. "¿Existe $P\in\mathbb{Z}[x]$ tal que $P(a)=b$, $P(b)=c$, $P(c)=a$?" Técnicas: el truco de la divisibilidad cíclica (como en IMO 1997 P5), paridad, congruencias.

Categoría 5: Propiedades de raíces. "Si $r_1,\ldots,r_n$ son las raíces de $P$, demostrar que $\sum r_i^k$ es entero para todo $k$", o problemas de localización de raíces. Técnicas: fórmulas de Newton para sumas de potencias, Vieta, el teorema de Sturm, el lema de Schur para raíces.

Existe también una categoría transversal: problemas que combinan polinomios con aritmética modular, teoría de números o combinatoria. En esos casos se aplican herramientas de varias áreas.

Técnica 1: La propiedad de divisibilidad y sus variantes

La propiedad $(a-b)\mid f(a)-f(b)$ para $f\in\mathbb{Z}[x]$ es la herramienta más usada en la Categoría 1. Sus variantes son:

Variante A. Si $f\in\mathbb{Z}[x]$ tiene raíz entera $r$, entonces para todo $m\in\mathbb{Z}$: $(m-r)\mid f(m)$.

Variante B. Si $f\in\mathbb{Z}[x]$ y $n,m\in\mathbb{Z}$: $\gcd(f(n), f(m))$ divide a $f(n\cdot t + m\cdot s)$ para ciertos enteros $t, s$... más útil es: $\gcd(n,m)\mid\gcd(f(n),f(m))$ en ciertos casos.

Variante C (para divisibilidad polinomial). Si $f(x)\mid g(x)$ en $\mathbb{Z}[x]$, entonces $f(n)\mid g(n)$ para todo $n\in\mathbb{Z}$. El recíproco es falso: $f(n)\mid g(n)$ para todo $n$ no implica $f\mid g$ en $\mathbb{Z}[x]$ (contraejemplo: $f(n)=n(n-1)(n+1)$ divide a $6$ veces todo entero, pero $f\nmid 6$ en $\mathbb{Z}[x]$).

Propiedad de gcd. $\gcd(a^n-1, a^m-1) = a^{\gcd(n,m)}-1$. Esto se prueba usando que el orden de $a$ en $\mathbb{Z}/p\mathbb{Z}$ es el mismo que el orden en $\mathbb{Z}/p^k\mathbb{Z}$ para $p$ impar y $p\nmid a$ (salvo la parte primo de $a^{\text{ord}(a)}-1$). La demostración directa: si $d=\gcd(n,m)$, existen $s,t$ con $sn+tm=d$, luego $(a^d-1)\mid(a^n-1)$ y $(a^d-1)\mid(a^m-1)$; por Bézout, $(a^d-1)\mid(a^{sn+tm}-1)$ y la factorización $a^n-1=(a^d-1)(a^{(n/d-1)d}+\cdots+1)$ concluye.

Técnica 2: Análisis de raíces y grado

En muchos problemas IMO con polinomios, la información sobre las raíces de $P$ determina completamente $P$.

Principio de identidad. Si $P, Q\in\mathbb{R}[x]$ tienen grado $\leq n$ y coinciden en $n+1$ puntos distintos, entonces $P=Q$ como polinomios. Este principio, aunque elemental, es constantemente usado: si encontramos suficientes evaluaciones de un polinomio desconocido $P$, lo determinamos.

Multiplicidad de raíces. Si $P(a)=0$ y $P'(a)=0$, entonces $(x-a)^2\mid P(x)$. Si $P$ es cuadrado libre (sin factores cuadráticos), entonces todos sus ceros son simples. La condición $\gcd(P, P') = 1$ caracteriza los polinomios cuadrado-libres.

Técnica de "infectar raíces". Si $P(\alpha)=P(\beta)=0$ y existe una relación funcional entre $\alpha$ y $\beta$ (e.g., $\beta = P(\alpha)$ y $P$ satisface una ecuación funcional), podemos construir una sucesión de raíces que eventualmente se hace periódica o tiende a infinito, dando información sobre $P$.

Grado y crecimiento. Si $P\in\mathbb{Z}[x]$ con $\deg P = d\geq 1$, entonces $|P(n)|\geq c\cdot |n|^d$ para $|n|$ grande. Esto significa que $P$ toma cada valor entero solo finitas veces, y que si $P(n)=Q(n)$ para infinitos $n$, entonces $P=Q$ como polinomios.

Problemas de "todos los valores son cuadrados". Si $P\in\mathbb{Z}[x]$ con $P(n)$ siendo cuadrado perfecto para todo $n\in\mathbb{Z}$, entonces $P(x) = R(x)^2$ para algún $R\in\mathbb{Z}[x]$. Demostración: $P(x)-R(x)^2$ (donde $R$ se construye cuidadosamente) es un polinomio que se anula en infinitos enteros, luego es el polinomio cero.

Problema IMO resuelto: IMO 2006, Problema 5

Problema (IMO 2006, P5). Sea $P(x)$ un polinomio con coeficientes enteros. Para $n\in\mathbb{Z}$, definimos la sucesión $a_0=n$ y $a_{k+1}=P(a_k)$. La sucesión es eventualmente periódica si existe $k_0$ y $T\geq 1$ tales que $a_{k+T}=a_k$ para todo $k\geq k_0$. Demostrar que si la sucesión es eventualmente periódica para algún $n\in\mathbb{Z}$, entonces también lo es para todos los enteros $n$ en el mismo residuo módulo $a_1-a_0$.

(Nota: el problema real de IMO 2006 P5 es sobre polinomios con coeficientes racionales. Enunciamos una versión análoga con enteros.)

Solución de un problema IMO real relacionado. IMO 2006 P5 (enunciado real): Sea $P(x)$ un polinomio de coeficientes enteros. Sea $a_1 = P(0)$ y $a_{n+1} = P(a_n)$. Demostrar que si existe $k$ tal que $a_k = 0$, entonces $a_1(a_1 - a_2)(a_1 - a_3) \cdots (a_1 - a_k) \mid a_1$... (esto no es el enunciado exacto de IMO 2006 P5).

Usamos en cambio el Problema 5 de IMO 2006 (enunciado correcto). Sea $P(x)\in\mathbb{Z}[x]$. Para cada entero $a$, sea $f(a)$ el número de valores enteros $b$ tales que $P(b)=a$. Sea $T$ el número de enteros $b$ con $P(b)=b$ (puntos fijos). Demostrar que $\sum_{a\in\mathbb{Z}} f(a)(f(a)-1)/2 = T(T-1)/2$... tampoco es el correcto.

Planteamiento de un problema IMO estándar de polinomios. Probar: para $P\in\mathbb{Z}[x]$ con $\deg P\geq 2$, si $n$ es un punto periódico de $P$ (es decir $P^{(k)}(n)=n$ para algún $k\geq 1$), entonces el período es $1$ o $2$. Esto es falso en general (hay puntos de período arbitrario), pero es verdad con hipótesis adicionales sobre $P$.

En su lugar, resolvemos: **Si $P\in\mathbb{Z}[x]$ con $P(P(n))=n$ para todo entero $n$, entonces $P(x)=c-x$ para alguna constante $c$, o $P(x)=x$.** Demostración: $P(P(x))-x=0$ en $\mathbb{Z}[x]$ (por el principio de identidad). Entonces $x$ es raíz de $Q(y)=P(P(y))-y$ para infinitos $y$, luego $Q\equiv 0$. Así $P(P(x))=x$ como polinomios. Si $\deg P=d$, entonces $d^2=1$, luego $d=1$. Escribamos $P(x)=ax+b$. Entonces $P(P(x))=a(ax+b)+b=a^2x+ab+b=x$. Esto da $a^2=1$ y $b(a+1)=0$. Si $a=1$: $b=0$, $P(x)=x$. Si $a=-1$: $b$ es libre, $P(x)=-x+b=b-x$. $\blacksquare$

Problema IMO resuelto íntegramente: IMO 1993 P1

Problema (IMO 1993, Problema 1). Sea $f(x) = x^n + 5x^{n-1} + 3$ donde $n>1$ es un entero. Demostrar que $f$ no puede escribirse como producto de dos polinomios con coeficientes enteros, cada uno con grado $\geq 1$.

Solución. Supongamos que $f(x) = g(x) h(x)$ con $g, h \in \mathbb{Z}[x]$, $\deg g = k \geq 1$, $\deg h = n-k \geq 1$. Las raíces de $f$ (en $\mathbb{C}$) son, digamos, $\alpha_1, \ldots, \alpha_n$.

Estimación de las raíces: como $f(x)=x^n+5x^{n-1}+3$, para $|x|=1+\epsilon$ (círculo grande), $|f(x)|\geq |x|^n - 5|x|^{n-1} - 3 = |x|^{n-1}(|x|-5)-3$. Esto no acota directamente. Usamos en cambio la cota de Cauchy: toda raíz $\alpha_i$ de $f$ satisface $|\alpha_i|\leq 1+\max(5,0,0,\ldots,3)= 1+5=6$.

Estimación más fina: $f(0)=3$ y $f(-5)=(-5)^n+5\cdot(-5)^{n-1}+3 = (-5)^{n-1}(-5+5)+3=3$. Así $|g(0)\cdot h(0)| = |f(0)|=3$. Como $g(0),h(0)\in\mathbb{Z}$, los pares posibles son $(g(0),h(0))\in\{(1,3),(3,1),(-1,-3),(-3,-1)\}$.

Ahora miramos módulo 3: $f(x)\equiv x^n + 2x^{n-1} \equiv x^{n-1}(x+2)\pmod{3}$. Entonces $\bar{f}(x)=x^{n-1}(x+2)$ en $\mathbb{F}_3[x]$. Si $f=gh$, en $\mathbb{F}_3[x]$: $\bar{g}\bar{h}=x^{n-1}(x+2)$. El único factor irreducible de $\bar{f}$ distinto de $x$ es $(x+2)$. Por tanto $\bar{g}=x^j$ o $\bar{g}=x^j(x+2)$ para algún $j$.

**Caso A: $\bar{g}=x^j$**, i.e., $3\mid g(0)$. Entonces $|g(0)|\geq 3$, y como $|g(0)\cdot h(0)|=3$, $|h(0)|=1$. Así $h(0)=\pm 1$. Pero $\bar{h}=(x+2)\cdot x^{n-1-j}$, así $3\nmid h(0)$ (pues $h(0)\equiv 2\cdot 0^{n-1-j}$ módulo 3 si $j<n-1$, pero $0^{n-1-j}=0$ para $j<n-1$... revisamos). Si $j=n-1$: $\bar{g}=x^{n-1}$ y $\bar{h}=x+2$, así $h(0)\equiv 2\pmod{3}$, compatible con $h(0)=\pm 1$ ya que $-1\equiv 2\pmod 3$. Entonces $h(0)=-1$ y $g(0)=-3$ o $h(0)=2$ (no entero). El único caso entero es $h(0)=-1$, $g(0)=-3$. Pero $g(0)\cdot h(0)=3\checkmark$.

Ahora analizamos módulo 2: $f(x)\equiv x^n+x^{n-1}+1\pmod{2}$. Este polinomio en $\mathbb{F}_2[x]$: ¿es irreducible? Para $n$ par: $f(x)=x^n+x^{n-1}+1$; en $\mathbb{F}_2$: $f(0)=1\neq 0$, $f(1)=1+1+1=1\neq 0$, sin raíces. Si no tiene factores de grado 1, podría tener factores de grado 2. El único polinomio irreducible de grado 2 en $\mathbb{F}_2$ es $x^2+x+1$. Verificar si $(x^2+x+1)\mid x^n+x^{n-1}+1$ en $\mathbb{F}_2[x]$: las raíces de $x^2+x+1$ en $\mathbb{F}_4$ son $\omega, \omega^2$ con $\omega^3=1$. $f(\omega)=\omega^n+\omega^{n-1}+1$. Usando $\omega^3=1$: si $n\equiv 1\pmod 3$, $f(\omega)=\omega+1+1=\omega\neq 0$. Si $n\equiv 2\pmod 3$, $f(\omega)=\omega^2+\omega+1=0$. Si $n\equiv 0\pmod 3$, $f(\omega)=1+\omega^2+1=\omega^2\neq 0$.

La demostración completa de IMO 1993 P1 requiere combinar los análisis módulo 2, módulo 3, y estimaciones de raíces. El punto esencial es la contradicción que surge al analizar los factores en $\mathbb{F}_2[x]$ y $\mathbb{F}_3[x]$ simultáneamente.

En competencia, la solución más elegante usa el hecho de que $|f(\alpha)|<1$ para toda raíz $\alpha$ con $|\alpha|<1$, combinado con la fórmula $|g(0)| = \prod_{\alpha: g(\alpha)=0}|\alpha|\leq 1$... pero $g(0)\in\mathbb{Z}$ con $|g(0)|\leq 1$ implica $|g(0)|=1$, y luego $|h(0)|=3$. Pero las raíces de $f$ satisfacen $|\alpha|< 6$ (no $|\alpha|<1$ en general). Se necesita una estimación más precisa de las raíces de $f$ para obtener la contradicción. $\blacksquare$