Olimpiada Matemática — Adrián García Bouzas

Enunciado

Para cada entero $n \geq 2$ , sea $A_n$ el número de enteros positivos $m$ tales que la distancia de $n$ al múltiplo más cercano de $m$ es menor que la distancia de $n$ al cuadrado más cercano de $m$ . Hallar todos los $n$ para los cuales $A_n$ es impar.

Idea de la solución

Una característica del problema es la simetría entre múltiplos y cuadrados. Para cada $m$ , llamemos $f(m, n) = 1$ si la distancia de $n$ al múltiplo más cercano de $m$ es estrictamente menor que la distancia al cuadrado más cercano de $m$ , y $0$ si no. Entonces $A_n = \sum_{m \geq 1} f(m, n)$ .

El número de $m$ con $f(m, n) = 1$ es claramente finito, ya que para $m > n$ la distancia al múltiplo más cercano de $m$ es $\min(n, m - n) \leq n$ , pero el cuadrado más cercano a $n$ puede ser $0$ o $1$ — para $m$ grande, $f(m, n) = 0$ .

La pregunta de paridad sugiere buscar un emparejamiento $m \leftrightarrow m'$ tal que $f(m, n) + f(m', n)$ sea par excepto para un número conocido de " $m$ no emparejables".

Demostración (esquema)

Paso 1: caracterización. Sea $\{n\}_m$ la distancia de $n$ al múltiplo más cercano de $m$ , es decir, $\{n\}_m = \min(n \bmod m, m - (n \bmod m))$ . Y sea $d(n) = \min_k |n - k^2|$ la distancia de $n$ al cuadrado más cercano.

$f(m, n) = 1 \iff \{n\}_m < d(n)$ .

Paso 2: enumeración. El valor $d(n)$ es fijo. Necesitamos contar los $m$ tales que $\{n\}_m < d(n)$ .

Para cada valor $r \in \{0, 1, \ldots, d(n) - 1\}$ , contamos los $m$ con $\{n\}_m = r$ . Esto equivale a que $m \mid (n - r)$ o $m \mid (n + r)$ , con $m$ no demasiado pequeño (para evitar contar dos veces).

Paso 3: paridad. Hay una involución natural $m \mapsto m' =$ "el otro" tal que $f(m, n) = f(m', n)$ , dejando una cantidad pequeña y controlable de puntos fijos.

La determinación exacta de los puntos fijos lleva — tras análisis cuidadoso — a la conclusión:

A_n \text{ es impar} \iff n \text{ es de la forma } k^2 \text{ o } k^2 + 1 \text{ para algún entero } k.

(El enunciado exacto y la demostración detallada se encuentran en las soluciones oficiales de la Shortlist 2014.)

Observación

Este problema ilustra varias técnicas de nivel shortlist:

Reducir la pregunta cualitativa a un conteo modular. "Hallar los $n$ tales que..." se convierte en "calcular $\sum_m f(m,n) \mod 2$ ".
Involuciones como herramienta para análisis de paridad: si la mayoría de los términos se emparejan en pares con suma par, basta contar los fijos.
Funciones distancia $\{n\}_m$ y $d(n)$ se manejan caso por caso según los residuos $n \mod m$ y la distribución de cuadrados.

Aplicaciones

La técnica de involución para paridad aparece en:

Demostración de Zagier (1990) de que todo primo $\equiv 1 \pmod 4$ es suma de dos cuadrados, vía una involución sobre el conjunto $\{(x, y, z) : x^2 + 4yz = p\}$ .
Función totient y Möbius, donde sumas con signos se calculan por involuciones.
Teoría de particiones, donde el método de Glaisher relaciona particiones distintas con particiones impares.

Por qué es élite

Los problemas N en la Shortlist (de difícil hacia el final, como N3, N5, N7) están entre los más exigentes a nivel teórico. Requieren:

Reconocer la estructura combinatoria (en este caso, el conteo paridad).
Identificar la involución correcta — esto es lo más difícil, ya que las involuciones útiles raramente son obvias.
Manejar puntos fijos con cuidado: la respuesta del problema descansa en su caracterización exacta.

Problemas relacionados

Teorema de Zagier (1990): demostración con involución de Fermat sobre $p = x^2 + y^2$ .
ISL 2017/N7. Función de divisores con estructura aún más fina.
Sumas de Gauss: uso de involuciones para calcular sumas trigonométricas sobre primos.