EGMO 2024 P5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
BR1

OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Medalla-FOFO Pascua 2024
Mensajes: 414
Registrado: Sab 28 Oct, 2023 1:33 pm
Medallas: 2
Nivel: 1

EGMO 2024 P5

Mensaje sin leer por BR1 »

Sea $\mathbb{N}$ el conjunto de enteros positivos. Encontrar todas las funciones $f:\mathbb{N}\to \mathbb{N}$ tales que para toda pareja de enteros positivos $(x,y)$ se cumplen las siguientes condiciones:

(i) $x$ y $f(x)$ tienen el mismo número de divisores positivos.
(ii) Si $x$ no divide a $y$ e $y$ no divide a $x$, entonces$$\operatorname{mcd}(f(x),f(y))>f(\operatorname{mcd}(x,y)).$$Aquí $\operatorname{mcd}(m,n)$ es el mayor entero que divide a $m$ y $n$.
ACLARACIÓN: $1$ no es primo
Emiliano Sosa

OFO - Medalla de Bronce-OFO 2021 OFO - Medalla de Plata-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024
Mensajes: 35
Registrado: Jue 28 Ene, 2021 8:27 pm
Medallas: 3
Nivel: 2

Re: EGMO 2024 P5

Mensaje sin leer por Emiliano Sosa »

Spoiler: mostrar
Como $1$ tiene solo un divisor, entonces $f(1)$ también deberá tener un solo divisor, pero el único natural que tiene un divisor es el $1$, ergo $f(1)=1$.
Ahora si llamamos $P(x,y) : mcd(f(x), f(y)) > f(mcd(x,y))$, entonces si evaluamos $P$ es dos primos $p$ y $q$ tenemos que
$P(p,q) : mcd(f(p), f(q)) > f(1) = 1$ lo que nos dice que $f(p)$ y $f(q)$ tienen algún factor primo en común (digamos $k$), pero por $(i)$ tenemos que ambos $f(p)$ y $f(q)$ son primos también, por lo que $f(p)=f(q)=k$.

Ahora vamos a probar un pequeño lemita:
Si $n$ tiene una cantidad prima de divisores, entonces $f(n) = k^{\tau (n) -1}$, donde $\tau (n)$ es la cantidad de divisores de $n$.
Para ver esto veamos que como $n$ tiene una cantidad prima de divisores, entonces $f(n)$ también, y los únicos números que tienen una cantidad prima de divisores son los de la forma $p^{q-1}$, con $p$ y $q$ primos, pues si $n = p_1^{\alpha _1}x$, donde $mcd(p,x)=1$ y $x>1$, se tiene que $\tau (n) = (\alpha_1 + 1)\tau (x)$, que no es primo. Entonces hay un único primo que divide a $f(n)$.
Ahora, evaluando en $P$, tenemos que
$P(n,q) : mcd(f(n), k) > f(1) = 1$ y como $k$ es primo tenemos que $mcd(f(n), k) = \{1,k \} \Rightarrow mcd(f(n), k)=k$ (pues si fuera $1$ no tendríamos la desigualdad). De modo que $k \mid f(n)$ y como habíamos visto que solo un primo dividía a $f(n)$, entonces $f(n)=k^{\tau(n)-1}$, demostrando nuestro lemita.

Ahora vamos a probar un lema más potente:
Si $mcd(f(x), k^r) > k^m$ (con $r>m$) y $m+2 > \frac{\tau(x)}{2}$, entonces $f(x) = k^{\tau(x)-1}$.
Como adentro del $mcd$ tenemos un $k^r$, entonces podemos decir que $mcd(f(x), k^r) = \{1,k, k^2, \dotsi , k^r \}$, pero como tiene que ser mayor a $k^m$, lo podemos reducir a que $mcd(f(x), k^r) = \{k^m, k^{m+1}, \dotsi , k^r \}$ de donde sale que $k^{m+1} \mid x$. Ahora si suponemos que $x = k^sy$ con $k$ e $y$ coprimos e $y>1$, entonces $\tau(x) = \tau(k^s)\tau(y) \geq \tau(k^{m+1})\tau(y) = (m+2)\tau(y) > \frac{\tau(x)}{2} \times 2 = \tau(x)$, lo que es absurdo.
Entonces el único primo que divide a $f(x)$ es $k$, y por $(i)$ se tiene entonces que $f(x) = k^{\tau(x)-1}$

Volviendo al problema, vamos a proceder con inducción. Supongamos que $f(x) = x^{\tau (x)-1}$ para todo entero $x$ con $\tau (x) \leq l$. El caso base son tanto el ejemplo con $1$ como con todos los primos. Veamos ahora para $\tau(x) = l+1$.

Caso 1: $x$ tiene un solo factor primo.
Diremos que $x= p^r$
Agarramos primos $q_1$ y $q_2$ tales que $q_1 > r$ y $q_2 \neq p$. Entonces por la hipótesis inductiva y nuestro primer lemita, tenemos que
$P(p^{r-1}q_2,p^{q_1-1}) : mcd(f(p^{r-1}q_2), f(p^{q_1-1})) = mcd(f(p^{r-1}q_2), k^{q_1 -1}) > f(mcd(p^{r-1}q_2,p^{q_1-1})) = f(p^{r-1}) = k^{r-1}$
Donde lo que nos importa es que $mcd(f(p^{r-1}q_2), k^{q_1 -1}) > k^{r-1}$ que por nuestro segundo lema, como $r-1+2 = r+1 > \frac{2r}{2} = \frac{\tau(p^{r-1}q_2)}{2}$, sale que $f(p^{r-1}q_2) = k^{2r-1}$ (pues $\tau(p^{r-1}q_2) = 2r$).
Por último
$P(p^{r-1}q_2,p^r) : mcd(f(p^{r-1}q_2), f(p^r)) = mcd(k^{2r-1}, f(p^r)) > f(mcd(p^{r-1}q_2,p^r)) = f(p^{r-1}) = k^{r-1}$, que nuevamente, como $r-1+2 =r+1 > \frac{r+1}{2} = \frac{\tau(p^r)}{2} $, tenemos que $f(x) = f(p^r) = k^r = k^{\tau(x)-1}$.

Caso 2: $x$ tiene $2$ o más factores primos.
Diremos que $x=p^{\alpha}q^{\beta}z$, con $\alpha \geq \beta$ y $z$ coprimo con $p$ y $q$. Entonces consideramos el número $t = p^{\alpha+1}q^{\beta-1}z$, y notemos que
$\tau(t) = (\alpha +2) \beta \tau(z) < (\alpha +1)(\beta +1) \tau(z) = \tau(x)$, por lo que $f(t) = k^{\tau(t) -1}$.
Por último
$P(x,t) : mcd(f(x), f(t)) = mcd(f(x), k^{\tau(t)-1}) > f(mcd(x,t)) = f(p^{\alpha} q^{\beta -1} z) = k^{(\alpha +1) \beta \tau(z) -1}$
Y faltaría demostrar que $(\alpha +1) \beta \tau(z) + 1 > \frac{\tau(x)}{2} = \frac{(\alpha +1)(\beta +1) \tau(z)}{2}$ para que con nuestro segundo lema se complete la demostración, que moviendo términos queda $2 > (\alpha +1) \tau(z) (1- \beta)$ y como $\beta \geq 1$, el lado derecho será menor o igual a $0$, satisfaciendo las condiciones necesarias del segundo lema. Entonces $f(x) = k^{\tau(x) -1}$ en este caso también.

De modo que, todas las funciones que cumplen con las condiciones del enunciado son $f(x) = k^{\tau(x)-1}$, donde $k$ es un primo a elección y $\tau(x)$ es la cantidad de divisores del número $x$.
Responder