COFFEE "Ariel Zylber" - Problema B

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
COFFEE
Mensajes: 83
Registrado: Vie 13 Mar, 2020 7:19 pm
Nivel: Exolímpico

COFFEE "Ariel Zylber" - Problema B

Mensaje sin leer por COFFEE »

Determinar todas las funciones $f:\mathbb{N}\to \mathbb{N}$ tales que$$p\text{ es divisor de }f(p-1)!f(n)+n^{f(p)}$$para todo par de enteros positivos $n, p$ con $p$ primo.
Avatar de Usuario
COFFEE
Mensajes: 83
Registrado: Vie 13 Mar, 2020 7:19 pm
Nivel: Exolímpico

Re: COFFEE "Ariel Zylber" - Problema B

Mensaje sin leer por COFFEE »

Solución Oficial:
Spoiler: mostrar
Usamos la notación $a\mid b$ que se lee "$a$ divide a $b$". Como todos los números son naturales, vamos a evaluar en los valores más chicos posibles para $n$ y $p$, considerando entonces $n=1$ y $p=2$ obtenemos que$$2\mid f(1)!f(1)+1$$entonces $f(1)!f(1)+1$ es par, por lo que $f(1)!f(1)$ es impar, ahora, vemos que si $f(1)\geq 2$ entonces $f(1)!$ es par, por lo que $f(1)!f(1)$ es par, pero esto es absurdo, entonces $f(1)<2$, y al ser natural resulta $f(1)=1$. Reemplazando entonces únicamente $n=1$ tenemos que para todo $p$ vale que$$p\mid f(p-1)!+1$$usando ahora la notación de congruencias, esto se traduce en $f(p-1)!+1\equiv 0\pmod p$, es decir$$f(p-1)!\equiv -1\pmod p$$de esta forma, la condición del enunciado es $-f(n)+n^{f(p)}\equiv 0\pmod p$, en otras palabras$$f(n)\equiv n^{f(p)}\pmod p$$de esto obtenemos que $n\equiv 0\pmod p$ si y sólo si $f(n)\equiv 0\pmod p$. Considerando entonces $n=q$ donde $q$ es primo, tenemos que si $p$ es primo y $p\neq q$, entonces $q^{f(p)}\not \equiv 0\pmod p$, por lo que $f(q)\not \equiv 0\pmod p$, así que el único primo que puede dividir a $f(q)$ es $q$, por lo que $f(q)=q^k$ para algún entero no negativo $k$, y esto vale para cualquier primo. Por lo tanto, $f(n)\equiv n^{f(p)}\equiv n^{p^k}\pmod p$, además, el Pequeño Teorema de Fermat nos dice que $n^p\equiv n\pmod p$, usando esto $k$ veces resulta $n^{p^k}\equiv n\pmod p$, entonces $f(n)\equiv n\pmod p$, es decir, $f(n)-n\equiv 0\pmod p$. Sea $p$ un primo tal que $p>|f(n)-n|$, entonces como $f(n)-n\equiv 0\pmod p$, la única posibilidad es que $f(n)-n=0$, por lo tanto, $f(n)=n$ es la única solución posible.

Para ver que funciona tenemos que verificar que $p\mid (p-1)!n+n^p$, es decir, $(p-1)!n+n^p\equiv 0\pmod p$. El Teorema de Wilson nos dice que $(p-1)!\equiv -1\pmod p$, y usando nuevamente el Pequeño Teorema de Fermat vemos que $n^p\equiv n\pmod p$, entonces tenemos que verificar que $-n+n\equiv 0\pmod p$, pero esto es cierto, entonces $f(n)=n$ es la única solución, y con eso estamos.
Martín Lupin

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Oro-OFO 2022 FOFO Pascua 2022 - Medalla-FOFO Pascua 2022 FOFO 12 años - Medalla-FOFO 12 años
OFO - Medalla de Oro-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 40
Registrado: Lun 20 May, 2019 10:26 am
Medallas: 12
Nivel: Exolímpico
Ubicación: Mar del Plata

Re: COFFEE "Ariel Zylber" - Problema B

Mensaje sin leer por Martín Lupin »

Solución:
Spoiler: mostrar
La única solución es $f(n)=n$. Voy a demostrar que cumple el enunciado.
Por el teorema de Wilson $(p-1)!\equiv -1\pmod{p}$ y por el pequeño teorema de Fermat $n^p\equiv n\pmod{p}$. Entonces $$(p-1)!n+n^p\equiv -n+n\equiv 0\pmod{p}$$ como queríamos demostrar. Ahora voy a demostrar que esta es la única solución.
Eligiendo $p=2$ y $n$ impar tenemos que $n^{f(2)}$ es impar, por lo que $f(1)!f(1)$ también es impar. Entonces $f(1)<2\Rightarrow f(1)=1$. Reemplazando $n=1$ obtenemos que $$f(p-1)!\equiv -1\pmod{p}$$
Luego la condición del enunciado es equivalente a $$p\mid n^{f(p)}-f(n)$$
Si elegimos $n$ no divisible por $p$, entonces $p\nmid f(n)$. Si elegimos $n$ divisible por $p$, entonces $p\mid f(n)$. Luego si elegimos $n=p$ no existe ningún primo $q\neq p$ tal que $q\mid f(p)$. Entonces para cada primo $p$ existe un $k_p\in \mathbb{N}$ tal que $f(p)=p^{k_p}$. Por el pequeño teorema de Fermat $$n^{f(p)}-f(n)=n^{p^{k_p}}-f(n)=(((n^p)^p)^{\dots})^p-f(n)\equiv n-f(n)\equiv 0\pmod{p}$$
Entonces se cumple que $$p\mid f(n)-n$$
Esto significa que para cada $n$, $f(n)-n$ es divisible por todos los primos, por lo que $f(n)-n=0\Rightarrow f(n)=n$ para todo $n\in \mathbb{N}$.
2  
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: COFFEE "Ariel Zylber" - Problema B

Mensaje sin leer por Sandy »

Bueno me compliqué un poquito capaz
Spoiler: mostrar
Tomando $n=1$: $p\mid f(p-1)!f(1)+1\Longrightarrow p\nmid f(p-1)!\Longrightarrow f(p-1)<p$.
Tomando en esto último $p=2$, nos queda $f(1)<2\Longrightarrow f(1)=1$.
Luego $p\mid f(p-1)!+1\Longrightarrow f(p-1)!\equiv -1 (p)$ (1)

Tomando $n=p-1$: $p\mid f(p-1)!f(p-1)+(p-1)^{f(p)}\Longrightarrow f(p-1)!f(p-1)+(p-1)^{f(p)}\overset{(1)}{\equiv} -f(p-1)+(-1)^{f(p)}\equiv 0 (p)$.
Pero los únicos valores congruentes a $1$ o $p-1$ módulo $p$, menores que $p$, son $1$ y $p-1$. Luego, para todo $p$, $f(p-1)\in\{1, p-1\}$.
Pero si $f(p-1)=1$ para algún $p$, entonces $f(p-1)!=1!=1\equiv -1 (p)\Longrightarrow p\mid 2\Longrightarrow p=2$. Pero $2-1=1$, luego $f(p-1)=p-1\forall p$. Esto cumple lo pedido ya que, por el teorema de Wilson, $(p-1)!\equiv -1(p)$

Luego la condición original queda: $(p-1)!f(n)+n^{f(p)}\equiv 0(p)\Longrightarrow n^{f(p)}-f(n)\equiv 0(p)$.2

Sea $g_p$ una raíz primitiva módulo $p$, con $p\geq 5$. Es claro que $g_p\not\equiv 0(p)$ y $g_p\not\equiv -1(p)$. Por el teorema de Dirichlet sobre progresiones aritméticas, sabemos que existen infinitos primos congruentes a $g_p+1$ en módulo $p$. Sea $q$ uno de ellos y tomemos $n=q-1\equiv g_p(p)$.
$(q-1)^{f(p)}-f(q-1)\equiv (q-1)^{f(p)}-(q-1)\equiv 0(p)$
$\Longrightarrow q-1\equiv (q-1)^{f(p)} (p)$.
Como $g_p\not\equiv 0(p)$, $q-1\not\equiv 0(p)$ y $gdc(q-1, p)=1$, luego podemos dividir por $q-1$ ambos lados.
$\Longrightarrow 1\equiv (q-1)^{f(p)-1} (p)$.
Como $q-1\equiv g_p(p)$, $f(p)-1\equiv 0 (p-1)$.
Pero, por el Pequeño Teorema de Fermat, esto implica que, para todo $p$ que no divida a $n$ (son infinitos para todo $n$), $n^{f(p)}\equiv n\times n^{f(p)-1}\equiv n\times 1\equiv n (p)$.
Luego 2 se transforma en $n-f(n)\equiv 0(p)$ para infinitos primos $p\geq 5$, luego $n-f(n)$ tiene infinitos divisores y, por ser finito para todo $n\in\mathbb{N}$, debe ser igual a $0$ para todo $n$.
Luego la única función que puede cumplir la condición es $f(n)=n$.
Chequeo:
$f(p-1)!f(n)+n^{f(p)}\equiv (p-1)!n+n^p\equiv -n+n\equiv 0 (p)\Longrightarrow p\mid f(p-1)!f(n)+n^{f(p)} \forall p,n$
1  
Fallo inapelable.
Avatar de Usuario
NPCPepe

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Carolina González
COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Medalla-FOFO 10 años
Mensajes: 81
Registrado: Lun 17 Jun, 2019 9:22 pm
Medallas: 8
Nivel: 3
Ubicación: Argentina

Re: COFFEE "Ariel Zylber" - Problema B

Mensaje sin leer por NPCPepe »

Sandy escribió: Lun 08 Jun, 2020 1:58 pm Bueno me compliqué un poquito capaz
Spoiler: mostrar
Tomando $n=1$: $p\mid f(p-1)!f(1)+1\Longrightarrow p\nmid f(p-1)!\Longrightarrow f(p-1)<p$.
Tomando en esto último $p=2$, nos queda $f(1)<2\Longrightarrow f(1)=1$.
Luego $p\mid f(p-1)!+1\Longrightarrow f(p-1)!\equiv -1 (p)$ (1)

Tomando $n=p-1$: $p\mid f(p-1)!f(p-1)+(p-1)^{f(p)}\Longrightarrow f(p-1)!f(p-1)+(p-1)^{f(p)}\overset{(1)}{\equiv} -f(p-1)+(-1)^{f(p)}\equiv 0 (p)$.
Pero los únicos valores congruentes a $1$ o $p-1$ módulo $p$, menores que $p$, son $1$ y $p-1$. Luego, para todo $p$, $f(p-1)\in\{1, p-1\}$.
Pero si $f(p-1)=1$ para algún $p$, entonces $f(p-1)!=1!=1\equiv -1 (p)\Longrightarrow p\mid 2\Longrightarrow p=2$. Pero $2-1=1$, luego $f(p-1)=p-1\forall p$. Esto cumple lo pedido ya que, por el teorema de Wilson, $(p-1)!\equiv -1(p)$

Luego la condición original queda: $(p-1)!f(n)+n^{f(p)}\equiv 0(p)\Longrightarrow n^{f(p)}-f(n)\equiv 0(p)$.2

Sea $g_p$ una raíz primitiva módulo $p$, con $p\geq 5$. Es claro que $g_p\not\equiv 0(p)$ y $g_p\not\equiv -1(p)$. Por el teorema de Dirichlet sobre progresiones aritméticas, sabemos que existen infinitos primos congruentes a $g_p+1$ en módulo $p$. Sea $q$ uno de ellos y tomemos $n=q-1\equiv g_p(p)$.
$(q-1)^{f(p)}-f(q-1)\equiv (q-1)^{f(p)}-(q-1)\equiv 0(p)$
$\Longrightarrow q-1\equiv (q-1)^{f(p)} (p)$.
Como $g_p\not\equiv 0(p)$, $q-1\not\equiv 0(p)$ y $gdc(q-1, p)=1$, luego podemos dividir por $q-1$ ambos lados.
$\Longrightarrow 1\equiv (q-1)^{f(p)-1} (p)$.
Como $q-1\equiv g_p(p)$, $f(p)-1\equiv 0 (p-1)$.
Pero, por el Pequeño Teorema de Fermat, esto implica que, para todo $p$ que no divida a $n$ (son infinitos para todo $n$), $n^{f(p)}\equiv n\times n^{f(p)-1}\equiv n\times 1\equiv n (p)$.
Luego 2 se transforma en $n-f(n)\equiv 0(p)$ para infinitos primos $p\geq 5$, luego $n-f(n)$ tiene infinitos divisores y, por ser finito para todo $n\in\mathbb{N}$, debe ser igual a $0$ para todo $n$.
Luego la única función que puede cumplir la condición es $f(n)=n$.
Chequeo:
$f(p-1)!f(n)+n^{f(p)}\equiv (p-1)!n+n^p\equiv -n+n\equiv 0 (p)\Longrightarrow p\mid f(p-1)!f(n)+n^{f(p)} \forall p,n$
Spoiler: mostrar
yo lo resolvi casi igual con teorema de dirichlet y wilson, pero el pequeño teorema de fermat no se necesita, cuando sabes que hay $q-1$ para cada resto mod $p$, se obtiene que cualquier $n$ es congruente a $n^{f(p)}$ $mod$ $p$ y por lo tanto cualquier $n$ es congruente a $f(n)$
$3=569936821221962380720^3+(-569936821113563493509)^3+(-472715493453327032)^3$: esta es la tercer menor solucion descubierta para la ecuación $a^3+b^3+c^3=3$ , las otras dos son $1^3+1^3+1^3=3$ y $4^3+4^3+(-5)^3=3$
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: COFFEE "Ariel Zylber" - Problema B

Mensaje sin leer por Sandy »

NPCPepe escribió: Lun 08 Jun, 2020 3:22 pm
Sandy escribió: Lun 08 Jun, 2020 1:58 pm Bueno me compliqué un poquito capaz
Spoiler: mostrar
Tomando $n=1$: $p\mid f(p-1)!f(1)+1\Longrightarrow p\nmid f(p-1)!\Longrightarrow f(p-1)<p$.
Tomando en esto último $p=2$, nos queda $f(1)<2\Longrightarrow f(1)=1$.
Luego $p\mid f(p-1)!+1\Longrightarrow f(p-1)!\equiv -1 (p)$ (1)

Tomando $n=p-1$: $p\mid f(p-1)!f(p-1)+(p-1)^{f(p)}\Longrightarrow f(p-1)!f(p-1)+(p-1)^{f(p)}\overset{(1)}{\equiv} -f(p-1)+(-1)^{f(p)}\equiv 0 (p)$.
Pero los únicos valores congruentes a $1$ o $p-1$ módulo $p$, menores que $p$, son $1$ y $p-1$. Luego, para todo $p$, $f(p-1)\in\{1, p-1\}$.
Pero si $f(p-1)=1$ para algún $p$, entonces $f(p-1)!=1!=1\equiv -1 (p)\Longrightarrow p\mid 2\Longrightarrow p=2$. Pero $2-1=1$, luego $f(p-1)=p-1\forall p$. Esto cumple lo pedido ya que, por el teorema de Wilson, $(p-1)!\equiv -1(p)$

Luego la condición original queda: $(p-1)!f(n)+n^{f(p)}\equiv 0(p)\Longrightarrow n^{f(p)}-f(n)\equiv 0(p)$.2

Sea $g_p$ una raíz primitiva módulo $p$, con $p\geq 5$. Es claro que $g_p\not\equiv 0(p)$ y $g_p\not\equiv -1(p)$. Por el teorema de Dirichlet sobre progresiones aritméticas, sabemos que existen infinitos primos congruentes a $g_p+1$ en módulo $p$. Sea $q$ uno de ellos y tomemos $n=q-1\equiv g_p(p)$.
$(q-1)^{f(p)}-f(q-1)\equiv (q-1)^{f(p)}-(q-1)\equiv 0(p)$
$\Longrightarrow q-1\equiv (q-1)^{f(p)} (p)$.
Como $g_p\not\equiv 0(p)$, $q-1\not\equiv 0(p)$ y $gdc(q-1, p)=1$, luego podemos dividir por $q-1$ ambos lados.
$\Longrightarrow 1\equiv (q-1)^{f(p)-1} (p)$.
Como $q-1\equiv g_p(p)$, $f(p)-1\equiv 0 (p-1)$.
Pero, por el Pequeño Teorema de Fermat, esto implica que, para todo $p$ que no divida a $n$ (son infinitos para todo $n$), $n^{f(p)}\equiv n\times n^{f(p)-1}\equiv n\times 1\equiv n (p)$.
Luego 2 se transforma en $n-f(n)\equiv 0(p)$ para infinitos primos $p\geq 5$, luego $n-f(n)$ tiene infinitos divisores y, por ser finito para todo $n\in\mathbb{N}$, debe ser igual a $0$ para todo $n$.
Luego la única función que puede cumplir la condición es $f(n)=n$.
Chequeo:
$f(p-1)!f(n)+n^{f(p)}\equiv (p-1)!n+n^p\equiv -n+n\equiv 0 (p)\Longrightarrow p\mid f(p-1)!f(n)+n^{f(p)} \forall p,n$
Spoiler: mostrar
yo lo resolvi casi igual con teorema de dirichlet y wilson, pero el pequeño teorema de fermat no se necesita, cuando sabes que hay $q-1$ para cada resto mod $p$, se obtiene que cualquier $n$ es congruente a $n^{f(p)}$ $mod$ $p$ y por lo tanto cualquier $n$ es congruente a $f(n)$
Spoiler: mostrar
Corregime si me equivoco, pero podrían no ciclar los $p-1$ restos tranquilamente, podría haber un ciclo de algo que no sea $p-1$ (a menos que uses el pequeño teorema de Fermat)
Fallo inapelable.
Avatar de Usuario
NPCPepe

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Carolina González
COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Medalla-FOFO 10 años
Mensajes: 81
Registrado: Lun 17 Jun, 2019 9:22 pm
Medallas: 8
Nivel: 3
Ubicación: Argentina

Re: COFFEE "Ariel Zylber" - Problema B

Mensaje sin leer por NPCPepe »

si pero se podía usar solo para comprobar el resultado.
$3=569936821221962380720^3+(-569936821113563493509)^3+(-472715493453327032)^3$: esta es la tercer menor solucion descubierta para la ecuación $a^3+b^3+c^3=3$ , las otras dos son $1^3+1^3+1^3=3$ y $4^3+4^3+(-5)^3=3$
Responder