Catálogo de primeros movimientos en TN olímpica

El problema del primer movimiento

En teoría de números olímpica, el mayor obstáculo no suele ser la falta de conocimiento técnico, sino la incertidumbre sobre cómo atacar el problema. Un gran porcentaje de problemas de nivel Iberoamericana y Cono Sur se resuelve con herramientas elementales aplicadas en el orden correcto.

El primer movimiento es la acción que transforma el problema original en un problema más simple o que revela la estructura clave. Elegir mal el primer movimiento puede llevarte a callejones sin salida; elegirlo bien a menudo convierte el problema en rutina.

Este catálogo presenta los primeros movimientos más frecuentes, organizados por el tipo de señal que el problema envía. No es un algoritmo: es un repertorio de posibilidades que el competidor experto reconoce rápidamente.

Señal 1: divisibilidad de expresiones algebraicas

Cuando el enunciado pide demostrar que $A \mid B$ o que cierta expresión siempre es divisible por $n$, los primeros movimientos son:

M1.1. Probar módulos pequeños. Evalúa la expresión módulo $2, 3, 4, 5, 7, 8, 9, 11$. A menudo un cálculo modular directo resuelve el problema o revela la estructura necesaria.

M1.2. Factorizar algebraicamente. Busca factorizaciones que exhiban el factor buscado: $a^n - b^n = (a-b)(a^{n-1}+\cdots+b^{n-1})$, $a^3 + b^3 = (a+b)(a^2-ab+b^2)$, $a^2 - b^2 = (a-b)(a+b)$.

M1.3. Usar LTE. Si la expresión es de la forma $a^n \pm b^n$ y $p \mid a - b$ (o $a + b$), el Lifting the Exponent calcula $v_p$ exactamente.

M1.4. Inducción. Para divisibilidad de expresiones con $n$ variable, la inducción con un paso cuidadoso suele funcionar.

Señal 2: existencia de soluciones enteras

Cuando el problema pide "encontrar todas las soluciones enteras" o "demostrar que no hay soluciones", los primeros movimientos son:

M2.1. Probar módulos para imposibilidad. Si la ecuación es imposible, a menudo módulo 4, 8, 3, 7 o 9 se detecta la contradicción. Sistematiza: prueba todos los valores de las variables módulo $m$ y verifica si alguna combinación satisface la ecuación.

M2.2. Cotar una variable. Si la ecuación es $f(x) = g(y)$ con $f$ y $g$ polinomios, a menudo se puede acotar: "para $x > C$, $f(x) > g(y)$ para todo $y \le x$". Esto deja finitos casos a verificar.

M2.3. Factorizar y analizar divisores. Reescribe la ecuación como $A \cdot B = C$ y analiza todos los pares de divisores de $C$.

M2.4. Paridad. Separa en casos según la paridad de las variables. A menudo un lado es siempre par y el otro impar, dando contradicción.

Señal 3: propiedades de primos

Cuando el problema involucra primos o pide demostrar algo sobre infinitos primos, los primeros movimientos son:

M3.1. Usar el Teorema Fundamental de la Aritmética. Todo entero $> 1$ tiene un primo divisor. Si $n > 1$, sea $p$ el menor primo divisor. ¿Qué propiedades tiene $p$?

M3.2. Suponer finitos y buscar contradicción (estilo Euclides). Si hay que demostrar infinitud de primos con cierta propiedad, suponer que son finitos ($p_1, \ldots, p_k$) y construir un entero que genera un primo distinto.

M3.3. Aritmética modular selectiva. Para primos $p \equiv a \pmod m$, usar residuos cuadráticos o el símbolo de Legendre para controlar qué primos pueden dividir a ciertas expresiones.

**M3.4. Estimaciones con $\pi(x)$.** Si el problema pide contar primos o comparar densidades, usar el Postulado de Bertrand o cotas elementales de $\pi(x)$.

Señal 4: ecuaciones con exponentes

Cuando la ecuación involucra potencias o exponentes variables ($a^n = b^m + c$, etc.), los primeros movimientos son:

**M4.1. Valuaciones $p$-ádicas.** Calcula $v_p$ de ambos lados para varios primos $p$. Las ecuaciones de la forma $p^a = q^b \cdot r + s$ a menudo se resuelven así.

M4.2. Cotas de crecimiento. Si $a^m = b^n$, las funciones $a^m$ y $b^n$ crecen a diferentes velocidades según $\log a / \log b$. La irracionalidad de $\log a / \log b$ (cuando $a, b$ no son potencias del mismo número) implica a lo sumo finitas soluciones.

**M4.3. Módulo $p^k$ para potencias altas.** Para ecuaciones del tipo $x^n \equiv k \pmod m$, a veces el análisis módulo $m = p^k$ para una potencia alta de primo da la restricción buscada.

M4.4. Descenso infinito. Para mostrar que $a^n + b^n = c^n$ u otras ecuaciones no tienen soluciones, el descenso infinito produce una solución más pequeña a partir de una solución hipotética.

Señal 5: funciones aritméticas

Cuando el problema involucra $\tau$, $\sigma$, $\phi$ u otras funciones aritméticas, los primeros movimientos son:

M5.1. Usar la fórmula explícita. Escribe $n = p_1^{a_1}\cdots p_r^{a_r}$ y aplica las fórmulas del Capítulo 7. A menudo la condición del problema restringe fuertemente los exponentes $a_i$.

M5.2. Probar con primos y potencias de primos. Si hay que encontrar todos los $n$ con cierta propiedad de $f(n)$, primero resuélvelo para $n = p^k$ y luego usa multiplicatividad para el caso general.

M5.3. Cota superior por la función. $\phi(n) \ge \sqrt{n/2}$ para $n$ suficientemente grande; $\tau(n) = O(n^\epsilon)$ para todo $\epsilon > 0$; $\sigma(n) \le n \ln n + n$ para $n \ge 1$. Estas cotas limitan los posibles $n$.

El árbol de decisión del competidor

Ante un problema de TN olímpica, el protocolo práctico es:

Paso 1 (5 min). Lee el enunciado, identifica las variables, clasifica el tipo de problema (divisibilidad, existencia, conteo, propiedades de primos, etc.).

Paso 2 (10 min). Experimenta con valores pequeños. Si el problema pide "todas las soluciones", encuentra las primeras manualmente. Si pide "demostrar que no hay", busca el módulo que lo descarta.

Paso 3 (15 min). Aplica el primer movimiento del catálogo más apropiado. Si no avanza, prueba el segundo. Mantén un registro de lo que ya intentaste.

Paso 4 (tiempo restante). Una vez identificada la estructura, redacta la solución con todos los casos cubiertos.

La experiencia con el catálogo se desarrolla resolviendo problemas variados y reflexionando explícitamente sobre por qué cada herramienta fue (o no fue) efectiva.