Acotaciones útiles en problemas olímpicos

La fórmula de Legendre: $v_p(n!)$

La **valuación $p$-ádica** de $n!$, denotada $v_p(n!)$, es el mayor exponente de $p$ que divide a $n!$. La fórmula de Legendre la calcula explícitamente:

$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots$

(La suma es finita pues $\lfloor n/p^k \rfloor = 0$ para $p^k > n$.) Demostración: $v_p(n!)$ cuenta los múltiplos de $p$ en $\{1,\ldots,n\}$ (que aportan $\lfloor n/p \rfloor$ factores $p$), más los múltiplos de $p^2$ (que aportan un factor $p$ extra cada uno: $\lfloor n/p^2 \rfloor$ factores adicionales), etc.

Fórmula alternativa. $v_p(n!) = \frac{n - s_p(n)}{p-1}$ donde $s_p(n)$ es la suma de los dígitos de $n$ en base $p$. Esto se sigue de la igualdad $\sum_{k \ge 1} \lfloor n/p^k \rfloor = (n - s_p(n))/(p-1)$.

Valuación de coeficientes binomiales

La valuación $p$-ádica del coeficiente binomial $\binom{m+n}{n}$ está dada por la fórmula de Kummer: $v_p\binom{m+n}{n}$ es igual al número de acarreos al sumar $m$ y $n$ en base $p$.

De la fórmula de Legendre: $v_p\binom{n}{k} = v_p(n!) - v_p(k!) - v_p((n-k)!) = \frac{s_p(k) + s_p(n-k) - s_p(n)}{p-1}$.

Consecuencia. $p \mid \binom{n}{k}$ si y solo si al sumar $k$ y $n-k$ en base $p$ se produce al menos un acarreo. En particular, $p \nmid \binom{n}{k}$ si y solo si cada dígito de $k$ en base $p$ es $\le$ el correspondiente dígito de $n$ (Teorema de Lucas).

Teorema de Lucas. $\binom{n}{k} \equiv \prod_{i} \binom{n_i}{k_i} \pmod{p}$ donde $n = \sum n_i p^i$ y $k = \sum k_i p^i$ son las representaciones en base $p$ (con $\binom{a}{b} = 0$ para $a < b$).

Acotaciones con el coeficiente central

El coeficiente binomial central $\binom{2n}{n}$ satisface las siguientes cotas, muy usadas en olimpiadas:

$\frac{4^n}{2\sqrt{n}} \le \binom{2n}{n} \le 4^n$.

La cota superior $\binom{2n}{n} \le 4^n$ se sigue de $(1+1)^{2n} = \sum \binom{2n}{k} \ge \binom{2n}{n}$. La cota inferior $\binom{2n}{n} \ge 4^n/(2\sqrt{n})$ se obtiene de la fórmula de Wallis: $\binom{2n}{n} \sim 4^n/\sqrt{\pi n}$.

Otra cota: $\binom{2n}{n} \ge \frac{4^n}{2n+1}$ (pues es el mayor de $2n+1$ sumandos en $\sum_{k=0}^{2n}\binom{2n}{k} = 4^n$).

Estas cotas permiten estimar la magnitud de $\binom{2n}{n}$ y aplicar el Postulado de Bertrand o argumentos de divisibilidad.

La desigualdad AM-GM y sus variantes enteras

En problemas de teoría de números con estimaciones, la desigualdad entre medias aritmética y geométrica ($\text{AM} \ge \text{GM}$) aparece a menudo en forma discreta:

$\frac{a_1 + a_2 + \cdots + a_k}{k} \ge \sqrt[k]{a_1 a_2 \cdots a_k}$

con igualdad si y solo si $a_1 = a_2 = \cdots = a_k$.

Aplicación al producto de divisores. Si $\tau(n) = k$, los $k$ divisores de $n$ satisfacen: su producto es $n^{k/2}$ (pues los divisores se emparejan: $d \cdot (n/d) = n$). La AM-GM da $\frac{\sigma(n)}{\tau(n)} \ge n^{1/2}$, es decir, $\sigma(n) \ge \tau(n) \sqrt{n}$.

Corolario. Si $n$ es perfecto ($\sigma(n) = 2n$), entonces $\tau(n) \ge 2\sqrt{n}/...$: de $\sigma(n) \ge \tau(n)\sqrt{n}$ y $\sigma(n) = 2n$ obtenemos $\tau(n) \le 2n/\sqrt{n} = 2\sqrt{n}$. Todo número perfecto tiene a lo sumo $2\sqrt{n}$ divisores.

Orden de magnitud de $\text{lcm}(1,2,\ldots,n)$

El mínimo común múltiplo de los primeros $n$ enteros positivos satisface $L(n) = \text{mcm}(1, 2, \ldots, n) = \prod_{p \le n} p^{\lfloor \log_p n \rfloor}$.

De la demostración del Postulado de Bertrand se obtiene $L(n) \ge 2^n / (2n)$ para $n$ suficientemente grande. De hecho, $L(n) = e^{\psi(n)}$ donde $\psi(n) = \sum_{p^k \le n} \log p$ es la función de Chebyshev $\psi$, y el TNP implica $\psi(n) \sim n$, es decir $L(n) \sim e^n$.

Aplicación olímpica. La identidad $\binom{2n}{n} = \frac{(2n)!}{(n!)^2}$ es divisible por $\frac{L(2n)}{L(n)^2}$... Más útil: $L(n) \mid \text{lcm}\binom{n}{0},\binom{n}{1},\ldots,\binom{n}{n}$. Y el entero $\frac{1}{n+1}\binom{2n}{n}$ (número de Catalan) es siempre entero.

Valuaciones $p$-ádicas en problemas de divisibilidad

Principio general. Para demostrar que $A \mid B$, es suficiente (y necesario) demostrar que $v_p(A) \le v_p(B)$ para todo primo $p$.

Fórmula del lifting the exponent (LTE). Para $p$ primo impar, $p \mid a - b$, $p \nmid a$, $p \nmid b$: $v_p(a^n - b^n) = v_p(a-b) + v_p(n)$. Para $p = 2$, $2 \mid a - b$: $v_2(a^n - b^n) = v_2(a-b) + v_2(a+b) + v_2(n) - 1$.

El LTE (también llamado "Lifting the Exponent Lemma" o LTE) es una de las herramientas de estimación más poderosas en olimpiadas de nivel Iberoamericana y Cono Sur.

Ejemplo. Demuestra que $1000 \mid 2^{1000} - 2^{100} + 2^{10}$... Mejor: para $p$ primo y $n = p^k$, $v_p(2^n - 1) = v_p(2^{p^k}-1)$. Por LTE (si $p$ impar y $p \mid 2^{p-1}-1$ por Fermat): $v_p(2^n-1) \ge k$. Este tipo de estimación aparece en decenas de problemas olímpicos.