Nacional 2018 P1 N3

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

OFO - Medalla de Plata-OFO 2017 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Mención-FOFO Pascua 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
OFO - Jurado-OFO 2023 OFO - Jurado-OFO 2024
Mensajes: 382
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 17
Nivel: Exolímpico

Nacional 2018 P1 N3

Mensaje sin leer por Monazo »

Sea $p$ un número primo y $r$ el resto de la división $p$ por $210$. Se sabe que $r$ es un número compuesto y que se puede escribir como suma de dos cuadrados perfectos distintos de cero. Hallar todos los primos menores que $2018$ que satisfacen estas condiciones.
Última edición por BrunZo el Mié 24 Ene, 2024 4:14 pm, editado 1 vez en total.
Razón: divisón > división
Soy una Estufa en Piloto
:shock:
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 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 609
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Nacional 2018 P1 N3

Mensaje sin leer por Turko Arias »

Spoiler: mostrar
Sea $(r, 210)=d$, tenemos que $p=210q+r$ para algún entero positivo $q$, con lo que, si $d$ no es $1$, $p$ sería divisible por $d$ y por ende no sería primo ($d$ no puedes ser igual a $p$ ya que en ese caso quedaría $r=p$ con lo que $r$ no sería compuesto). Notamos que $\varphi(210)=\varphi(2.3.5.7)=\varphi(2)\varphi(3)\varphi(5)\varphi(7)=48$. Por otro lado chequeamos en nuestra tabla de números primos (es un Certamen Nacional así que todos tenemos una :lol: :lol: :lol: ) que hay $42$ números primos menores que $210$ coprimos con $210$, pero $r$ es compuesto, con lo que quedan $6$ valores posibles para $r$, que son $1, 121, 143, 169, 187$ y $209$. Como $r$ es compuesto, descartamos el $1$, y como $r$ es suma de cuadrados perfectos, por esta fantástica propiedad podemos descartar al $143$, al $187$ y al $209$. Por otro lado, la propiedad nos habla de suma de cuadrados NO NEGATIVOS, por lo que el $121$ en principio podría servir, pero a mano verificamos que no hay dos cuadrados no nulos que sumen $121$. Luego, el único valor posible es $r=169$, ya que $169=12^2+5^2$. Chequeamos ahora nuevamente en nuestra lista de primos (que en serio hay que tener una impresa para el Nacional :roll: :roll: :roll: ) si alguno de los números de la forma $210q+169$ menores que $2018$ es primo:
$379 \checkmark \\
589 \\
799 \\
1009 \checkmark \\
1219 \\
1429 \checkmark \\
1639 \\
1849 $

Y eso es todo amigos :D
2  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
usuario250

OFO - Jurado-OFO 2015
Mensajes: 238
Registrado: Vie 30 Dic, 2011 12:30 pm
Medallas: 1

Re: Nacional 2018 P1 N3

Mensaje sin leer por usuario250 »

Spoiler: mostrar
Para los 6 valores posibles de r, se podría haber hecho un tanteo medio rápido de cuál es la factorización por primos de cada r, teniendo en cuenta que 210 = 2*3*5*7, entonces ni 2, ni 3, ni 5, ni 7 divide a r y solo queda buscar las posibles factorizaciones por primos para números menores a 210 que no contengan los primos antes mencionados (y que no sean números primos :P).
Turko Arias escribió: Vie 30 Nov, 2018 11:39 pm
Spoiler: mostrar
Sea $(r, 210)=d$, tenemos que $p=210q+r$ para algún entero positivo $q$, con lo que, si $d$ no es $1$, $p$ sería divisible por $d$ y por ende no sería primo ($d$ no puedes ser igual a $p$ ya que en ese caso quedaría $r=p$ con lo que $r$ no sería compuesto). Notamos que $\varphi(210)=\varphi(2.3.5.7)=\varphi(2)\varphi(3)\varphi(5)\varphi(7)=48$. Por otro lado chequeamos en nuestra tabla de números primos (es un Certamen Nacional así que todos tenemos una :lol: :lol: :lol: ) que hay $42$ números primos menores que $210$ coprimos con $210$, pero $r$ es compuesto, con lo que quedan $6$ valores posibles para $r$, que son $1, 121, 143, 169, 187$ y $209$. Como $r$ es compuesto, descartamos el $1$, y como $r$ es suma de cuadrados perfectos, por esta fantástica propiedad podemos descartar al $143$, al $187$ y al $209$. Por otro lado, la propiedad nos habla de suma de cuadrados NO NEGATIVOS, por lo que el $121$ en principio podría servir, pero a mano verificamos que no hay dos cuadrados no nulos que sumen $121$. Luego, el único valor posible es $r=169$, ya que $169=12^2+5^2$. Chequeamos ahora nuevamente en nuestra lista de primos (que en serio hay que tener una impresa para el Nacional :roll: :roll: :roll: ) si alguno de los números de la forma $210q+169$ menores que $2018$ es primo:
$379 \checkmark \\
589 \\
799 \\
1009 \checkmark \\
1219 \\
1429 \checkmark \\
1639 \\
1849 $

Y eso es todo amigos :D
Peznerd
Mensajes: 113
Registrado: Jue 07 Jul, 2016 1:04 pm
Nivel: 3
Contactar:

Re: Nacional 2018 P1 N3

Mensaje sin leer por Peznerd »

Turko Arias escribió: Vie 30 Nov, 2018 11:39 pm
Spoiler: mostrar
Notamos que $\varphi(210)=\varphi(2.3.5.7)=\varphi(2)\varphi(3)\varphi(5)\varphi(7)=48$.
¿Qué significa ésto? Parece una notación para coprimos, pero no la entiendo. Help again please!
Un día vi una vaca sin cola vestida de uniforme

$$\int u \, dv=uv-\int v \, du\!$$
muebalee
Mensajes: 2
Registrado: Jue 09 Jun, 2022 11:53 pm
Nivel: 3

Re: Nacional 2018 P1 N3

Mensaje sin leer por muebalee »

yo lo pense asi:
Spoiler: mostrar
primero obtuve las posibles sumas de cuadrados perfectos menores a 210, y tache aquellas que tengan divisores comunes con 210. me quedo una lista de 22 numeros y tache los numeros no-compuestos, y quedaron los posibles "r" (117;153;169). Luego fui sumando estos posibles "r" a los multiplos de 210 menores a 2018, y aquellas sumas que se encontraban en la lista de numeros primos eran los numeros que respondian a las condiciones planteadas por el enunciado.
No es una resolucion creativa, pero es la forma en la que se puede resolver sin usar teoria de libros hechos por personas que estaban al pedo hace miles de años
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024 FOFO 14 años - Mención-FOFO 14 años
Mensajes: 1083
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: 3
Contactar:

Re: Nacional 2018 P1 N3

Mensaje sin leer por drynshock »

Spoiler: mostrar
P = r + 210c

Notemos que "r" puede tomar los valores desde 0 hasta 209


210 = 2.3.5.7, entonces "r" no puede ser multiplo de los factores primos de 210 ya que si no P no sería primo.

Sabiendo esto podemos restringir los valores de "r" a 11 y 13 ¿Por que no mas? Por el teorema de Fermat para que un numero pueda expresarse como suma de cuadrados los factores primos de la forma 4k+3 deben estar elevados a una potencia par, como 4.2+3=11 entonces la única opción posible de que "r" tenga a 11 en su factorizacion en primos es que r=11². Luego, si queremos que aparezca un numero mayor o igual a 17, este debería estar acompañado de otro factor, pero veamos que el mas chico posible, es decir el 13, nos da en la multiplicacion 13.17=221 por lo que nos pasamos de 209.

Entonces los unicos valores posibles de "r" son 11² y 13² (por alguna razón que desconozco 11² no puede expresarse como suma de de 2 cuadrados distintos sin contar el 0, si alguno explica le agradezco) en cambio 13² sí.

Retomando a 210.c + 13² = p, podemos ir probando valores de c y vemos que los valores que cumplen son:
P={379, 1009, 1429}


@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
Avatar de Usuario
drynshock

FOFO 13 años - Mención-FOFO 13 años OFO - Medalla de Bronce-OFO 2024 FOFO Pascua 2024 - Copa-FOFO Pascua 2024 FOFO 14 años - Mención-FOFO 14 años
Mensajes: 1083
Registrado: Sab 21 May, 2022 12:41 pm
Medallas: 4
Nivel: 3
Contactar:

Re: Nacional 2018 P1 N3

Mensaje sin leer por drynshock »

drynshock escribió: Dom 24 Dic, 2023 4:42 pm
Spoiler: mostrar

(por alguna razón que desconozco 11² no puede expresarse como suma de de 2 cuadrados distintos sin contar el 0, si alguno explica le agradezco)
Eso es porque el
Spoiler: mostrar
Teorema de navidad de Fermat inlcuye al cero en la suma, es decir $11^2=11^2+0^2$ es válido, pero en este problema como no pueden haber ceros, entonces debemos checkearlo a mano.
Mañana (en un horario prudente), edito este mensaje y pongo una solución con latex (casi se me caen los ojos leyendo la solución vieja).
@Bauti.md ig
First place is winning, anything else is losing.
"Alexandra Trusova"
Responder