Selectivo IMO 2019 - Problema 5

Avatar de Usuario
Matías V5

Colaborador OFO - Jurado FOFO 6 años - Jurado
Mensajes: 904
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 6
Nivel: Exolímpico

Selectivo IMO 2019 - Problema 5

Mensaje sin leer por Matías V5 » Vie 12 Abr, 2019 8:12 pm

Sean $\mathbb N$ el conjunto de los números naturales y $f : \mathbb N \to \mathbb N$ una función tal que
i) $f(mn)=f(m)f(n)$ para todos $m,n$ en $\mathbb N$;
ii) $m+n$ divide a $f(m)+f(n)$ para todos $m,n$ en $\mathbb N$.
Demostrar que existe un número natural impar $k$ tal que $f(n)=n^k$ para todo $n$ en $\mathbb N$.
"La geometría es el arte de hacer razonamientos correctos a partir de figuras incorrectas." -- Henri Poincaré

maxiR

OFO - Mención FOFO 8 años - Mención Especial OFO - Medalla de Bronce
Mensajes: 21
Registrado: Vie 26 Ene, 2018 3:30 pm
Medallas: 3
Nivel: 1
Ubicación: Barrancas

Re: Selectivo IMO 2019 - Problema 5

Mensaje sin leer por maxiR » Vie 12 Abr, 2019 11:28 pm

Mi solucion en la prueba.
Spoiler: mostrar
Recordando la funcion clásica de cauchy (4) y viendo que el dominio es $N$,vemos que en $ i)$de debe ser $f(x)=x^\alpha$ ,con $\alpha $ entero positivo.Remplazando en esto en $ii)$ , $m+n/m^\alpha+n^\alpha$.Es conocido que $m+n$ divide a $m^\alpha+n^\alpha$ con $\alpha$ par, si y solo si $m=n$.Pero la ii) se cumple para todos los $m$ y $n$ naturales.Contradiccion.Luego $\alpha$ es impar.y es facil ver que $f(n)=n^k$, con impar cumple k$ las condiciones.
Última edición por maxiR el Sab 13 Abr, 2019 12:48 am, editado 1 vez en total.

maxiR

OFO - Mención FOFO 8 años - Mención Especial OFO - Medalla de Bronce
Mensajes: 21
Registrado: Vie 26 Ene, 2018 3:30 pm
Medallas: 3
Nivel: 1
Ubicación: Barrancas

Re: Selectivo IMO 2019 - Problema 5

Mensaje sin leer por maxiR » Sab 13 Abr, 2019 12:47 am

maxiR escribió:
Vie 12 Abr, 2019 11:28 pm
Mi solucion en la prueba.
Spoiler: mostrar
Recordando la funcion clásica de cauchy (4) y viendo que el dominio es $N$,vemos que en $ i)$de debe ser $f(x)=x^\alpha$ ,con $\alpha $ entero positivo.Remplazando en esto en $ii)$ , $m+n/m^\alpha+n^\alpha$.Es conocido que $m+n$ divide a $m^\alpha+n^\alpha$ con $\alpha$ par, si y solo si $m=n$.Pero la ii) se cumple para todos los $m$ y $n$ naturales.Contradiccion.Luego $\alpha$ es impar.y es facil ver que $f(n)=n^k$, con impar cumple k$ las condiciones.

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro FOFO 8 años - Jurado OFO - Jurado
Mensajes: 366
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 9
Nivel: 2

Re: Selectivo IMO 2019 - Problema 5

Mensaje sin leer por jujumas » Sab 13 Abr, 2019 1:22 am

Creo que esto no anda.
maxiR escribió:
Vie 12 Abr, 2019 11:28 pm
Mi solucion en la prueba.
Spoiler: mostrar
Recordando la funcion clásica de cauchy (4) y viendo que el dominio es $N$,vemos que en $ i)$de debe ser $f(x)=x^\alpha$ ,con $\alpha $ entero positivo.Remplazando en esto en $ii)$ , $m+n/m^\alpha+n^\alpha$.Es conocido que $m+n$ divide a $m^\alpha+n^\alpha$ con $\alpha$ par, si y solo si $m=n$.Pero la ii) se cumple para todos los $m$ y $n$ naturales.Contradiccion.Luego $\alpha$ es impar.y es facil ver que $f(n)=n^k$, con impar cumple k$ las condiciones.
Spoiler: mostrar
El argumento central de la solución es que si una función completamente multiplicativa va de $N$ a $N$, debe ser $f(x)=x^\alpha$ ,con $\alpha$ entero positivo, pero esto es mentira.

A modo de contraejemplo, tomamos $f$ tal que para cada $n$, $f$ intercambie el exponente del primo $2$ con el del primo $3$ en $n$. De este modo, expresando $m$ como $2^{a_1}3^{a_2}x$ y $n$ como $2^{b_1}3^{b_2}y$ con $x$ e $y$ coprimos con $6$, tenemos que

$f(m)f(n)=(2^{a_2}3^{a_1}x)(2^{b_2}3^{b_1}y)$

$f(mn)=f(2^{a_1+b_1}3^{a_2+b_2}xy)=2^{a_2+b_2}3^{a_1+b_1}xy$

y es fácil ver que estos son iguales.

maxiR

OFO - Mención FOFO 8 años - Mención Especial OFO - Medalla de Bronce
Mensajes: 21
Registrado: Vie 26 Ene, 2018 3:30 pm
Medallas: 3
Nivel: 1
Ubicación: Barrancas

Re: Selectivo IMO 2019 - Problema 5

Mensaje sin leer por maxiR » Sab 13 Abr, 2019 2:45 am

sisi tenes razon...ahi le pifie

Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata OFO - Medalla de Oro
Mensajes: 247
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 3
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Selectivo IMO 2019 - Problema 5

Mensaje sin leer por Turko Arias » Sab 13 Abr, 2019 2:49 am

Spoiler: mostrar
Sea $P(m,n)$ la proposición $f(mn)=f(m)f(n)$ y $Q(m,n)$ la proposición $m+n | f(m)+f(n)$.
$P(1,1): f(1)=f(1)^2$ y como estamos trabajando en naturales, $f(1)=1$.
Vamos a probar ahora que ningún primo impar divide a $f(2):$
Sea $p$ un primo impar, tenemos $Q(p-1,1)$ nos dice que $p | f(p-1)+1$, por otro lado, $P(\frac{p-1}{2}, 2)$ nos dice que $f(p-1)=f(2)f(\frac{p-1}{2})$, combinando ambos resultados tenemos $p | f(2)f(\frac{p-1}{2})+1$, o equivalentemente $ f(2)f(\frac{p-1}{2}) \equiv -1(p)$ de donde $f(2) \not\equiv 0(p)$, pero $p$ era cualquier primo impar, luego $f(2) \not\equiv 0(p)$ para todo primo impar. Si $f(2)=1$ entonces $Q(1,2)$ nos dice que $1+2 | f(1)+f(2)=2$ absurdo, luego $f(2)>1$ y no tiene divisores primos impares, luego $f(2)=2^k$ para algún $k$ entero positivo. Ahora bien $P(2,2)$ nos dice que $f(2^2)=f(2)^2$. Iterando este proceso tenemos que $P(2^n, 2)$ nos dice que $f(2^{n+1})=f(2^n)f(2)=f(2)^nf(2)=f(2)^{n+1}$, por lo que podemos deducir que $f(2^n)=(2^k)^n=2^{kn}$. Ahora bien $Q(2,4)$ nos dice que $f(2)+f(4)=f(2)+f(2^2)=2^k+2^{2k}=2^k+4^k \equiv 0(6)$, pero notamos que $2^k \equiv 2(6)$ si $k$ es impar y $2^k \equiv 4(6)$ si $k$ es par. Por otro lado notamos que $4^k \equiv 4(6)$ para todo $k$ entero positivo, luego $2^k+4^k \equiv 0(6)$ implica que $k$ es impar.
Ahora bien, vamos a hacer una observación: notamos que si tenemos un entero $x$ tal que $x \equiv 0(m)$ para infinitos $m$ entonces $x=0$ es la única solución, ya que de no ser cero, siempre podemos afirmar que $m \leq |x|$, pero como hay infinitos $m$, entonces $|x|$ puede ser tan grande como nosotros queramos, pero si fuera un entero positivo eso sería imposible, luego $x=0$ es la única solución. Vamos a usar esto ahora para probar que $f(n)=n^k$:
$Q(n, 2^a)$, con $a$ entero positivo, nos dice que $n+2^a | f(n)+2^{ak}$. Recordamos por otro lado que si $k$ es impar, $n^k+(2^a)^k=(n+2^a)(n^{k-1}-(2^a)^1n^{k-2}+(2^a)^2n^{k-3}...-(2^a)^{k-2}n+(2^a)^{k-1})$, lo que nos permite concluir que $n+2^a | n^k+(2^a)^k=n^k+2^{ak}$. Restando ambos datos llegamos a que $n+2^a | f(n)+2^{ak}-(n^k+2^{ak})=f(n)-n^k$. Ahora bien, como $a$ puede ser cualquier entero positivo tenemos que $n+2^a | f(n)-n^k$ para todo entero positivo $a$, luego $f(n)-n^k$ tiene infinitos divisores distintos, por lo que aplicando la observación, podemos concluir que $f(n)-n^k=0$ de donde $f(n)=n^k$. Pero $n$ era un entero positivo, que podría ser reemplazado por cualquier entero positivo, luego la igualdad $f(n)=n^k$ vale para todo entero positivo, y ya habíamos probado que $k$ tenía que ser impar, por lo que hemos finalizado $\blacksquare$
1  

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 914
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo IMO 2019 - Problema 5

Mensaje sin leer por Gianni De Rico » Sab 13 Abr, 2019 6:47 pm

Turko Arias escribió:
Sab 13 Abr, 2019 2:49 am
Spoiler: mostrar
Recordamos por otro lado que si $k$ es impar, $n^k+(2^a)^k=(n+2^a)(n^{k-1}-(2^a)^1n^{k-2}+(2^a)^2n^{k-3}...-(2^a)^{k-2}n+(2^a)^{k-1})$, lo que nos permite concluir que $n+2^a | n^k+(2^a)^k=n^k+2^{ak}$.
Una forma de ver esto en caso de no conocer esa fórmula
Spoiler: mostrar
Sean $a$ y $b$ enteros, y sea $k$ un entero positivo impar. Luego $$a+b\equiv 0\pmod{a+b}\Rightarrow a\equiv -b\pmod{a+b}\Rightarrow a^k\equiv (-b)^k\pmod{a+b}\underset{k\text{ impar}}{\Rightarrow} a^k\equiv -b^k\pmod{a+b}\Rightarrow a^k+b^k\equiv 0\pmod{a+b}$$
Por lo que $a+b\mid a^k+b^k$ para todos $a$ y $b$ enteros y $k$ entero positivo impar.
[math]

Avatar de Usuario
Prillo

Colaborador OFO - Jurado
Mensajes: 398
Registrado: Sab 18 Dic, 2010 8:52 pm
Medallas: 2

Re: Selectivo IMO 2019 - Problema 5

Mensaje sin leer por Prillo » Dom 14 Abr, 2019 2:32 pm

Spoiler: mostrar
Por la condicion (i), $f(n^t) = f(n)^t$ para todo $n, t \in \mathbb N$. Ahora $f(1) = f(1)^2 \Rightarrow f(1) = 1$. Veamos que $m - n | f(m) - f(n)$ para todos $m > n \ge 1$. Sea $a > m$, tenemos que $m - n | a(m - n) | f(m) + f(a(m - n) - m)$ y $m - n | (a - 1)(m - n) | f(n) + f((a - 1)(m - n) - n)$ entonces como $a(m - n) - m = (a - 1)(m - n) - n$, restando nos queda que $m - n | f(m) - f(n)$. Ahora sean $p \neq q$ primos y supongamos que $q | f(p)$. Luego $p^{q - 1} - 1 | f(p)^{q - 1} - 1$, absurdo por Fermat. Luego $f(p)$ es una potencia de $p$ para todo $p$ primo. Por ultimo sean $p \neq q$ primos y supongamos que $f(p) = p^i, f(q) = q^j$ ($i, j \ge 0$). Sea $t$ arbitrariamente grande. Luego $p^t - q | f(p)^t - f(q) = p^{it} - q^j \equiv q^i - q^j$ (porque $p^t \equiv q \text{ (mod $p^t - q$)}$). Como $t$ es arbitriamente grande, $i = j$. Luego existe $k \in \mathbb N_0$ tal que $f(p) = p^k$ para todo $p$ primo, y por (i), $f(n) = n^k$ para todo $n \in \mathbb N$. Ademas, $k$ debe ser impar porque $2 + 1 | 2^k + 1$. Finalmente, es claro que todo $k$ impar anda.
1  

Responder