$f$ es sobreyectiva puede, de hecho, ser reemplazado por $f(1) = 1$. Solución: Demostraremos que $f(n) = n$ es la única solución. Además, denotaremos $p | m \iff p | n$ para todo primo $p$ como $m \sim n$. Note que la condición del problema se traduce en $f(m + n) \sim f(m) + f(n)$ para todo natural $m$ y $n$. Lema 1: Si $p$ es algún primo, $p | f(n)$, y $k \in \mathbb{Z}^+$, entonces $p | f(kn)$. Demostración: Inducción sobre $k$. El caso base se da en el enunciado del problema. Para la hipótesis inductiva, tenemos $p | f(kn)$ y $p | f(n)$, por lo tanto $p | f(kn) + f(n)$, lo que da $p | f((k + 1)n)$. Lema 2: $f(1) = 1$. Demostración: Si $f(1) \neq 1$, sea $p | f(1)$, donde $p$ es primo. Entonces nuestro lema implica que $p | f(n)$ para todo natural $n$; pero entonces, existe un $n$ tal que $f(n) = 1$, contradiciendo la sobreyectividad de $f$. Por lo tanto, debemos tener $f(n) = 1$. Lema 3: $f(2^k)$ es una potencia de 2 para todo $k$ no negativo. Demostración: Usamos inducción. $k = 0$ es simplemente el lema 2. Para la hipótesis inductiva, tenemos que $p | f(2^{k + 1})$ significa $p | f(2^k) + f(2^k)$, lo cual es el doble de una potencia de 2, lo que significa $p = 2$. Por lo tanto, $f(2^{k + 1})$ debe ser una potencia de 2. Lema 4: Si $f(n) = 1$, entonces $n = 1$. Demostración: Suponga que $n > 1$. Entonces $f(n - 1) + 1 \sim f(n) = 1$, por lo que $f(n - 1) + 1$ no tiene factores primos, lo cual es claramente imposible. Lema 5: $f(2) = 2$ y $f(3) = 3$. Demostración: Por el lema 4, podemos dejar $f(2) = 2^b$ para algún natural $b$. Ahora, $f(3) + f(1) \sim f(3 + 1)$, que es una potencia de 2. Por lo tanto, $f(3) + 1$ debe ser una potencia de 2, así que $f(3) = 2^a - 1$ para algún entero positivo $a$. Además, $2^b + 1 = f(2) + f(1) \sim f(3) = 2^a - 1$, es decir, $2^b + 1$ y $2^a - 1$ tienen el mismo conjunto de factores primos. Si $b = 3$, entonces $2^b + 1 = 9$, por lo que $2^a - 1$ debe ser una potencia de 3 mayor que 1. Por lo tanto, $2^a - 1 = 3^y$, para algún entero $y$. $y > 0$, así que tomar esto módulo 3 revela que $a$ es par. Consecuentemente, $(2^{\frac{a}{2}} - 1)(2^{\frac{a}{2}} + 1) = 3^y$. Por lo tanto, $2^{\frac{a}{2}} = 1$, dando $a = 2$, así que debemos tener $a = 2$ en este caso. Si $b \neq 3$, entonces demostraremos que $a = 2b$. Si $a > 2b$, entonces por el teorema de Zsigmondy, existe algún primo $p$ tal que el orden de 2 módulo $p$ es $a$. Si $p | 2^b + 1$, entonces $p | 2^{2b} - 1$. Pero entonces, $2b < a$, lo cual contradice la minimalidad de $a$. Si $a < 2b$, entonces por el teorema de Zsigmondy, existe algún primo $p$ tal que el orden de 2 módulo $p$ es $2b$. Por lo tanto, $p | 2^{2b} - 1 = (2^b - 1)(2^b + 1)$. $p | 2^b - 1$ contradiría la minimalidad de $2b$, así que debemos tener $p | 2^b + 1$. Si $p | 2^a - 1$ también, dado que $a < 2b$, la minimalidad de $2b$ es contradicha. Por lo tanto, debemos tener que $a = 2b$. En esta situación, tenemos que $2^b + 1$ y $2^{2b} - 1 = (2^b + 1)(2^b - 1)$ tienen los mismos factores primos, es decir, $2^b + 1$ y $2^b - 1$ tienen los mismos factores primos. Pero si $p | 2^b - 1$ y $p | 2^b + 1$, $p$ primo, entonces $p | 2$; pero $2 \nmid 2^b - 1$, así que debemos tener $b = 1$. Consecuentemente, $a = 2$. Por lo tanto, podemos concluir que $(a,b) = (2,1)$ o $(a,b) = (2,3)$. En otras palabras, $f(3) = 3$ y $f(2) = 2$ o $f(2) = 8$. Suponga por contradicción que $f(2) = 8$. Entonces $11 = f(2) + f(3) \sim f(5) \sim f(4 + 1) \sim f(4) + f(1) = 2^c + 1$, para algún natural $c$ (ya que $f(4)$ es una potencia de 2). Por lo tanto, $2^c + 1$ es una potencia de 11. Pero $2^c = 11^z - 1$ para algún entero $z$ es imposible, ya que 5 divide a $11^z - 1$, aunque no divide a una potencia de 2. Por lo tanto, podemos concluir que $f(2) = 2$, lo que completa la demostración de este lema. Lema 6: Sea $S_p$ el conjunto de todos los $m$ tales que $f(m)$ es un múltiplo de $p$, y sea $m_0$ su elemento más pequeño (el cual, por la sobreyectividad de $f$, necesariamente existe). Entonces, si $n \in S_p$, entonces $m_0 | n$. Demostración: Escriba $n = m_0q + r$, con $r < m_0$. Suponga por contradicción que $r \neq 0$. Entonces $p | f(n)$ implica que $p | f(n - m_0) + f(m_0)$. Dado que $p | f(m_0)$, tenemos $p | f(n - m_0)$. Podemos repetir esto hasta obtener $p | f(r)$. Pero $r < m_0$, contradiciendo la minimalidad de $m_0$. Por lo tanto, $m_0 | n$, como se deseaba. Lema 7: $f$ es inyectiva. Demostración: Suponga que $f(a) = f(b)$ para algunos naturales $a$ y $b$, con $a \leq b$. Entonces $f(a + k) \sim f(a) + f(k) = f(b) + f(k) \sim f(b + k)$, para todo natural $k$. Suponga que $a + k$ es primo. Sea $q$ cualquier factor primo de $f(a + k)$, y sea $m_0$ el elemento más pequeño en $S_q$. Por el lema 6, $m_0 | a + k$. Pero $a + k$ es primo, y $m_0 \neq 1$, así que $a + k = m_0$. Pero $q | f(a + k)$ implica que $q | f(b + k)$, ya que las dos funciones comparten factores primos. Por lo tanto, $b + k \in S_q$, así que $a + k = m_0 | b + k$, es decir, $a + k | b - a$ para todo $k$ tal que $a + k$ es primo. Si $b > a$, tomando cualquier primo $p > b + a$ y estableciendo $k = p - a$ da $p | b - a$, lo que significa $b + a < p \leq b - a$, lo cual es una contradicción. Por lo tanto, $a = b$, lo que completa nuestra demostración. Lema 8: Si $q$ es cualquier entero mayor que 3, y $n$ es un entero mayor que 1, entonces $q^n - 1$ tiene un factor primo que $q - 1$ no tiene. Demostración: Dado que $q > 3$, $q \neq 2$. Si $n = 2$ y $q^2 - 1 = (q - 1)(q + 1)$ y $q - 1$ tienen los mismos factores primos, $q + 1$ y $q - 1$ deben tener los mismos factores primos. Pero el único factor primo que podrían compartir es 2 (ya que cualquier factor dividiría a su diferencia), así que $q + 1$ y $q - 1$ son ambos potencias de 2. Se sigue trivialmente que $q$ debe ser igual a 3, lo cual contradice nuestra suposición de que $q > 3$. Ahora, debido a que $q, n > 2$, por el teorema de Zsigmondy existe un primo $p$ tal que el orden de $q$ módulo $p$ es $n$. Por lo tanto, $p | q^n - 1$. Si $p | q - 1$, entonces el orden de $q$ módulo $n$ debe ser 1, lo cual contradice nuestra suposición de que $n > 1$. Por lo tanto, $p \nmid q - 1$, lo que completa la demostración de este lema. Procederemos por inducción fuerte para demostrar que $f(n) = n$ para todos los enteros $n$. El caso base está cubierto en los lemas 2 y 5. Suponga ahora que existe algún $n \geq 3$ tal que para todo $k$ entre 1 y $n$ inclusive, tenemos $f(k) = k$. Por el postulado de Bertrand, existe algún primo $q$ entre $n$ y $2n$ exclusivo. Se sigue que $n$ y $q - n$ yacen ambos entre 1 y $n$ inclusive, así que $f(q) = f(n + q - n) \sim f(n) + f(q - n) = q$, es decir, $f(q)$ es una potencia de $q$, digamos, $q^m$. Debido a que $q < 2n$, $q + 1 \leq 2n$. Por lo tanto, $n$ y $q + 1 - n$ yacen ambos entre 1 y $n$ inclusive, así que $f(q + 1) = f(n + q + 1 - n) \sim f(n) + f(q + 1 - n) = q + 1$, así que $f(q + 1)$ y $q + 1$ comparten los mismos factores primos. Por otro lado, $f(q + 1) \sim f(q) + 1 = q^m + 1$, así que $q + 1$ y $q^m + 1$ deben tener los mismos factores primos. Suponga por contradicción que $m > 1$. Entonces $2m > 2$, y claramente $q \neq 2$, así que por el teorema de Zsigmondy existe algún primo $p$ tal que $2m$ es el orden de $q$ módulo $p$. Por lo tanto, $p | q^{2m} - 1 = (q^m - 1)(q^m + 1)$. No puede dividir a $q^m - 1$, ya que $2m$ fue elegido para ser minimal, así que $p | q^m + 1$. Pero $q + 1$ y $q^m + 1$ tienen los mismos factores primos, así que $p | q + 1$ también, dando $p | q^2 - 1$. Se sigue que $2m$, el orden, debe por lo tanto dividir a 2. Por lo tanto, $m = 1$, así que nuestra suposición de que $m \neq 1$ es falsa. Podemos concluir desde aquí que $f(q) = q$. Si $q = n + 1$, entonces hemos terminado. De lo contrario, podemos suponer que $q > n + 1$. Considere el entero $q - 1$. Note que $n < q - 1 < 2n$ (ya que supusimos que $q > n + 1$), así que $n$ y $q - 1 - n$ yacen entre 1 y $n$ inclusive. Por lo tanto, $f(q - 1) = f(n + q - 1 - n) \sim f(n) + f(q - 1 - n) = n + q - 1 - n = q - 1$. Pero $f(q - 1) + f(1) \sim f(q) = q$, así que $f(q - 1) = q^j - 1$ para algún entero positivo $j$. Por lo tanto, $q - 1 \sim q^j - 1$, así que tienen los mismos divisores primos. Note que $q > n + 1 \geq 4 > 3$, así que por el lema 8, debemos tener que $j = 1$. Por lo tanto, $f(q - 1) = q - 1$. Si $q = n + 2$, entonces hemos terminado. De lo contrario, podemos suponer que $q > n + 2$. Queda por demostrar que $f(n + 1) = n + 1$. Por el lema 7, $f(n + 1) < n + 1$ contradiría la inyectividad de $f$, así que $f(n + 1) \geq n + 1$. Suponga por contradicción que $f(n + 1) > n + 1$. Sea $f(n + 1) = n + 1 + z$, donde $z$ es algún entero no negativo. Entonces $1 \leq q - n - 2, q - n - 1 \leq n$ (ya que $n + 2 < q < 2n$). De esto, se puede ver que $q + z = f(n + 1) + f(q - n - 1) \sim f(n + 1 + q - n - 1) = f(q) \sim q$ y que $q + z - 1 = f(n + 1 + q - n - 2) = f(q - 1) \sim q - 1$. De $q + z \sim q$, tenemos que $q + z = q^i$ para algún natural $i > 1$ (o de lo contrario $z = 0$). Pero entonces, tenemos que $q^i - 1 = q + z - 1 \sim q - 1$. Como antes, $q > n + 1 \geq 4 > 3$, así que por el lema 8, tenemos que $i = 1$, así que $z = 0$. Por lo tanto, $f(n + 1) = n + 1$, lo que completa nuestra demostración.

2007 IMO Shortlist 2007 P5

Problemas Recomendados

Recomendaciones