Problemas tipo ONEM

Estrategia general ante un problema diofántico

Cuando enfrentamos una ecuación diofántica en una olimpiada, el primer paso es identificar el tipo. Las preguntas guía son: ¿la ecuación es lineal o no lineal? ¿Hay factorizaciones evidentes? ¿El lado derecho es cero o un entero específico? ¿El enunciado pide "todas las soluciones" o "demostrar que no hay soluciones"?

Las herramientas que tenemos disponibles en este nivel son: (1) Bézout y solución general para ecuaciones lineales. (2) Factorización $(x-y)(x+y) = n$ o similares para cuadráticas. (3) Argumentos de congruencia para descartar soluciones módulo algún entero conveniente. (4) Descenso infinito para demostrar inexistencia. (5) Acotaciones: si $f(x,y) = n$ y $f$ crece, hay finitos candidatos.

En muchos problemas de la ONEM, la técnica correcta se identifica en 1-2 minutos con práctica. El reto es ejecutarla sin errores aritméticos.

Tipo 1: ecuaciones con factorización directa

Muchas ecuaciones de olimpiada se resuelven factorizando la expresión y usando que si $ab = n$ con $a, b$ enteros positivos, hay finitas posibilidades.

Ejemplo 1: "Halla todos los pares de enteros positivos $(x, y)$ tales que $xy - x - y = 1$." Sumamos 1 a ambos lados y factorizamos: $xy - x - y + 1 = 2$, es decir $(x-1)(y-1) = 2$. Las factorizaciones de 2 en enteros positivos son $1 \times 2$ y $2 \times 1$. Así $(x-1, y-1) \in \{(1,2),(2,1)\}$, dando $(x,y) \in \{(2,3),(3,2)\}$.

Ejemplo 2: "Determina todos los enteros positivos $n$ tales que $n^2 + 4n + 4$ sea primo." Observamos $n^2 + 4n + 4 = (n+2)^2$. Un cuadrado perfecto solo es primo si es $p^2 = p$, imposible para $p \ge 2$. Así no hay solución.

La técnica de "completar un cuadrado" o "agregar una constante para factorizar" es muy poderosa: permite transformar expresiones difíciles en productos.

Tipo 2: ecuaciones lineales con restricciones enteras

Ejemplo 3: "¿De cuántas maneras se puede pagar exactamente $S/\ 37$ usando monedas de $S/\ 3$ y billetes de $S/\ 5$, sin recibir cambio?" Buscamos enteros no negativos $x, y$ con $3x + 5y = 37$.

La solución general de $3x + 5y = 37$: una solución particular es $x_0 = 4, y_0 = 5$ (verificar: $12+25=37$). Solución general: $x = 4 + 5t$, $y = 5 - 3t$. Para $x \ge 0$: $t \ge -4/5$, así $t \ge 0$. Para $y \ge 0$: $5 - 3t \ge 0$, así $t \le 5/3$, es decir $t \le 1$. Valores: $t \in \{0, 1\}$. Soluciones: $(x,y) = (4,5)$ y $(9,2)$. Hay exactamente 2 maneras.

Ejemplo 4: "Halla todos los enteros $m, n$ tales que $6m + 10n = 22$." Dividimos por $\gcd(6,10) = 2$: $3m + 5n = 11$. Solución particular: $(m_0, n_0) = (7, -2)$ (pues $21 - 10 = 11$). General: $m = 7 + 5t$, $n = -2 - 3t$, $t \in \mathbb{Z}$.

Tipo 3: demostrar inexistencia con congruencias

Cuando el enunciado dice "demuestra que no existen...", la primera herramienta es buscar un módulo conveniente que haga la ecuación imposible.

Ejemplo 5: "Demuestra que $x^2 + y^2 = 2023$ no tiene solución entera." Trabajamos módulo 4: los cuadrados son $\equiv 0$ o $1 \pmod 4$, así $x^2 + y^2 \equiv 0, 1$ o $2 \pmod 4$. Pero $2023 = 4 \cdot 505 + 3 \equiv 3 \pmod 4$. Como $3$ no está entre $\{0,1,2\}$, no hay solución.

Ejemplo 6: "Demuestra que no existen enteros positivos $a, b$ con $a^2 - b^2 = 6$." Como $a^2 - b^2 = (a-b)(a+b) = 6$ y $a - b$ y $a + b$ tienen la misma paridad, su producto es par si ambos son pares (dando múltiplo de 4) o impar si ambos son impares. Pero $6 \equiv 2 \pmod 4$: ni es múltiplo de 4 ni es impar. Imposible.

La elección del módulo es un arte: módulo 4 resuelve problemas con cuadrados; módulo 3 o 7 puede resolver problemas con cubos; módulo $p$ para primos específicos es útil cuando el enunciado menciona ese primo.

Tipo 4: acotación y verificación caso a caso

Cuando el conjunto de soluciones candidatas es finito y manejable, la estrategia es acotar las variables y verificar.

Ejemplo 7: "Halla todos los enteros positivos $x$ tales que $x^2 + 2x + 1 = y^2$ para algún entero $y$." Reescribimos: $(x+1)^2 = y^2$, es decir $(y - (x+1))(y + (x+1)) = 0$. Como $y, x > 0$, $y + x + 1 > 0$, así $y = x + 1$ (tomando la raíz positiva). Todas las soluciones son $y = x+1$ para cualquier entero positivo $x$.

Ejemplo 8: "¿Existen enteros $a, b \ge 1$ tales que $a^2 + b = 2024$ y $a + b^2 = 2024$?" Restando las dos ecuaciones: $a^2 - a = b^2 - b$, es decir $a(a-1) = b(b-1)$, o $(a-b)(a+b-1) = 0$. Así $a = b$ (pues $a + b - 1 \ge 1 > 0$). Sustituyendo: $a^2 + a = 2024$. Discriminante: $1 + 4 \cdot 2024 = 8097$. $\sqrt{8097} \approx 89.98$, que no es entero. Así no existe solución entera.

La integración de todas las técnicas —congruencias, factorización, acotación, descenso— es lo que distingue una resolución olímpica elegante de una solución por fuerza bruta.