Selectivo IMO 2019 - Problema 5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Matías V5

Colaborador-Varias OFO - Jurado-OFO 2015 OFO - Jurado-OFO 2016 FOFO 6 años - Jurado-FOFO 6 años OFO - Jurado-OFO 2017
OFO - Jurado-OFO 2018 OFO - Jurado-OFO 2020
Mensajes: 957
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
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-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Bronce-OFO 2019
Mensajes: 25
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-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Bronce-OFO 2019
Mensajes: 25
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 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020
Mensajes: 394
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 11
Nivel: Exolímpico

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-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Bronce-OFO 2019
Mensajes: 25
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-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 OFO - Jurado-OFO 2020
Mensajes: 359
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 5
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$
2  

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 OFO - Jurado-OFO 2020
Mensajes: 1174
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 3
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.
Queda Elegantemente Demostrado

Avatar de Usuario
Prillo

Colaborador-Varias OFO - Jurado-OFO 2015
Mensajes: 400
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.
2  

HelcsnewsXD

FOFO 9 años - Mención Especial-FOFO 9 años
Mensajes: 34
Registrado: Jue 13 Sep, 2018 8:59 am
Medallas: 1
Nivel: 2

Re: Selectivo IMO 2019 - Problema 5

Mensaje sin leer por HelcsnewsXD » Jue 12 Mar, 2020 12:13 pm

Spoiler: mostrar
$\exists f: \mathbb{N} \rightarrow \mathbb{N}$ / $\forall m,n \in \mathbb{N}$, $f(mn)=f(m)f(n)$, $m+n\mid {f(m)+f(n)}$
Como $f(n)$ es completamente multiplicativa, $f(1)=1 \Rightarrow m+1\mid {f(m)+1}$. Y si $m=n$, entonces $f(m^2)={f(m)}^2$ y ${2m}\mid {2f(m)} \Rightarrow m\mid {f(m)} \Rightarrow f(m)=mk$ / $ k \in \mathbb{N}$. Ahora, tenemos dos opciones, que $k$ dependa de $m$ o no. En el último caso, por $f(1)$ sacamos que $k=1$, por lo que $f(m)=m$ cumple. Ahora, hay que ver cuando $k$ depende de $m$.
Observando $f(m^2)=m^2k_{m^2}={f(m)}^2={mk_m}^2=m^2{k_m}^2$, tenemos $k_{m^2}={k_m}^2$. Ahora, como $k$ depende de $m$, consideraremos $k=m^rc$ donde $r,c \in \mathbb{N}$ y $c$ es un número constante. Por esto, reemplazando tenemos:
$k_{m^2}={k_m}^2 \Rightarrow m^{r_1}c=(m^{r_2}c)^2 \Rightarrow m^{r_1}c=m^{2r_2}c^2 \Rightarrow$ Como $c$ es constante y no depende de $m$, $c=1$.
De esto tenemos $m^{r_1}=m^{2r_2}$. Por esto, $f(m^2)=m^2m^{r_1}=m^2(m^{r_2})^2$ y $f(m)=m\times m^{r_2}$, cumpliéndose esto. Ahora, ya tenemos $f(m)=m^k$ con $k \in \mathbb{N}$. Solo queda demostrar que $k$ siempre es impar.
Sabemos que $m+n\mid {m^k+n^k} \Rightarrow$ si $m=2$ y $n=1$, entonces $3\mid 2^k+1$. Como tenemos que $2^2\equiv 1 \pmod 3$, siempre que $k$ sea par, $2^k\equiv 1\pmod 3$. Esto es lo que hace que $2\equiv 2\pmod 3$ y $2\times 2^2=2^3\equiv 2\pmod 3$ y hace que se cumpla el ciclo para todo $k$ impar.
De este modo tenemos que $\forall n,k \in \mathbb{N}$ / $k\equiv 1\pmod 2$, $f(n)=n^k$.

Responder