Provincial 2015 P2 N3

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
3,14

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Medalla de Plata-OFO 2018
FOFO 9 años - Jurado-FOFO 9 años
Mensajes: 457
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 6
Nivel: Exolímpico

Provincial 2015 P2 N3

Mensaje sin leer por 3,14 »

Determinar cuántos enteros [math] tienen la siguiente propiedad:
Para cada [math], el resto de dividir [math] por [math] es mayor o igual que [math].
[math]
Avatar de Usuario
JPablo
Mensajes: 361
Registrado: Lun 25 Mar, 2013 9:00 pm
Nivel: Exolímpico

Re: Provincial 2015 P2 N3

Mensaje sin leer por JPablo »

Las cuentas del final no las voy a hacer porque son fáciles, largas, aburridas y rutinarias. Voy a desarrollar el planteo de las mismas y sus resoluciones quedan a cargo del interesado :P
Spoiler: mostrar
Para [math] el resto debe ser mayor o igual a [math], la única posibilidad es [math]

Para [math] el resto debe ser mayor o igual que [math], la única posibilidad es [math]

Para [math] el resto debe ser mayor o igual que [math]. Como teníamos ya que [math] entonces la única posibilidad es [math]. Ahora nos podemos olvidar de la condición sobre [math].

Para [math] se tiene que el resto debe ser mayor o igual que [math]. Las únicas posibilidades son [math] y [math]

Para [math] el resto ya quedó determinado por [math] e [math], y nos queda [math] que satisface la condición.

Para [math] el resto debe ser mayor o igual que [math], las únicas posibilidades son [math], [math] y [math]

Para [math] el resto debe ser mayor o igual que [math], pero como ya teníamos [math] entonces la única posibilidad es [math] y nos olvidamos de la condición sobre [math].

Para [math] el resto debe ser mayor o igual que [math], pero teníamos [math], luego las únicas posibilidades son [math] y [math] y nos olvidamos de la condición sobre [math].

Para [math] el resto ya queda determinado por los casos [math] e [math]. Sin embargo, [math] implica [math], lo cual no puede ser. En cambio, [math] implica [math] y eso sí puede ser.

En conclusión, nos quedaron los siguientes sistemas:

[math]
[math]
[math]
[math]

Son [math] sistemas de ecuaciones con módulos coprimos dos a dos. Por el Teorema Chino del Resto se pueden resolver cada uno de ellos y luego proceder rutinariamente para ver cuántos naturales menores que [math] satisfacen la condición. No voy a hacerlo porque es la parte fácil, larga y aburrida del problema :P
1  
LuchoLP

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Plata-OFO 2017
Mensajes: 191
Registrado: Mié 17 Abr, 2013 7:27 pm
Medallas: 3
Nivel: Exolímpico

Re: Provincial 2015 P2 N3

Mensaje sin leer por LuchoLP »

Espero no haber pifiado en alguna cuenta :P
Spoiler: mostrar
En principio por la condición del enunciado los restos posibles en la división de [math] por [math] son:

[math]
[math]
[math]
[math]
[math]
[math]
[math]
[math]
[math]

La primer condición nos dice que [math] es impar entonces descartamos que [math] tenga resto: [math] mod [math], [math] mod [math], [math] mod [math], [math] mod [math], [math] mod [math], [math] mod [math]. Como [math] tiene resto [math] mod [math], descartamos [math] mod [math], [math] mod [math] y [math] mod [math]. Como [math] tiene resto [math] mod [math], descartamos [math] mod [math]. Como [math] tiene resto [math] mod [math], descartamos [math] mod [math] y [math] mod [math]. Como [math] tiene resto [math] mod [math], descartamos [math] mod [math].

Ahora bien, como [math] tiene resto [math] mod [math] y [math] mod [math] digamos [math], de lo que [math] debe ser de la forma [math], es decir que [math], que es el dato que ya sabíamos. Es decir que los datos de los restos en la división por [math] y por [math] están "de más".
De la misma forma, como [math] tiene resto [math] mod [math] y [math] mod [math] llegamos a que esto equivale a que [math] tenga resto [math] mod [math], y esto también nos dice que el dato de resto [math] mod [math] ya no nos interesa.
De que tiene resto [math] mod [math] y [math] mod [math] se llega a que [math] debe tener resto [math] mod [math]. Y sabiendo que [math] tiene resto [math] mod [math] y [math] mod [math], concluímos que tiene resto [math] mod [math].

Ahora los posibles restos quedaron así:
[math]
[math]
[math]

De las primeras dos se determinan los posibles restos en la división por [math], quedando:
[math]
[math]

De esto sale que [math] debe ser tal de tener en la división por [math] resto [math].
De los primeros [math] casos tenemos [math] valores posibles para [math] en cada uno, y en los últimos dos casos tenemos [math] valores posibles para [math] en cada uno. Esto totaliza un total de [math] valores posibles para [math], que es la respuesta al problema.
Avatar de Usuario
3,14

OFO - Medalla de Plata-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Medalla de Oro-OFO 2017 OFO - Medalla de Plata-OFO 2018
FOFO 9 años - Jurado-FOFO 9 años
Mensajes: 457
Registrado: Jue 11 Oct, 2012 5:20 pm
Medallas: 6
Nivel: Exolímpico

Re: Provincial 2015 P2 N3

Mensaje sin leer por 3,14 »

Lo hice exactamente como JPablo. :)
1  
[math]
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: Provincial 2015 P2 N3

Mensaje sin leer por NPCPepe »

LuchoLP, A mi me dio 4762 porque puede tener mas restos en la division por 2520, son 12:
383
1103
2183
503
1223
1943
599
1679
2399
719
1439
2519
$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
drynshock

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

Re: Provincial 2015 P2 N3

Mensaje sin leer por drynshock »

Spoiler: mostrar
Independientes

j = 2
$N \equiv 1 (mod 2)$

j = 3
$N \equiv 2 (mod 3)$

j = 5
$N \equiv 3, 4 (mod 5)$

j = 7
$\boxed{N \equiv 4, 5, 6 (mod 7)}$

Teorema chino del resto

j = 4
$N \equiv 2, 3 (mod 4)$
Pero como $x \equiv 1 (mod 2)$ entonces sabemos que:
$N \equiv 3 (mod 4)$

j = 6
Sabiendo que:
$N \equiv 1 \equiv -1 (mod 2)$
$N \equiv 2 \equiv -1 (mod 3)$

Se llega a que $\boxed{N \equiv -1 \equiv 5 (mod 6)}$ por lo tanto, cumple la consigna.

j = 8
Sabiendo que:
$N \equiv 3 (mod 4)$

Se llega a que:
$N \equiv 3, 7 (mod 8)$

Sin embargo solamente cumple $\boxed{N \equiv 7 (mod 8)}$

j = 9
Sabiendo que:
$N \equiv 2 (mod 3)$

Se llega a que:
$N \equiv 2, 5, 8 (mod 9)$

Sin embargo solamente cumplen los casos $\boxed{N \equiv 5, 8 (mod 9)}$

j = 10
Caso 1)
$N \equiv 1 \equiv 3 (mod 2)$
$N \equiv 3 (mod 5)$

$\therefore N \equiv 3 (mod 10)$
$\Rightarrow \Leftarrow$

Concluimos entonces que $x \not \equiv 3(mod 5)$

Caso 2)
$N \equiv 1 \equiv -1 (mod 2)$
$N \equiv 4 \equiv -1 (mod 5)$

$\therefore \boxed{N \equiv -1 \equiv 9 (mod 10)}$ el cual cumple



Teorema chino del resto final
Sabiendo que:
$N \equiv 4 (mod 5)$
$N \equiv 5, 8 (mod 9)$
$N \equiv 7 (mod 8)$
$N \equiv 4, 5, 6 (mod 7)$

Veamos que con $5, 9, 8$ y $7$ podemos formar todos los demás casos $(2, 3, 4, 6)$. Además, como $5, 9, 8$ y $7$ son todos coprimos entre si, entonces sabemos que hay una única solución para cada resto, precisamente $2$ restos del $9$ y $3$ restos del $7$. Esto nos deja con un aproximado de $\lfloor \frac{10^6}{2520} \rfloor.6 = 2376$ números que satisfacen.

Ahora nos queda ver cuantos números satisfacen entre $2520.396 = 997,920$ y $10^6$ o lo que vendría a ser igual a calcular los casos entre $0$ y $2080$.

Por teorema chino del resto con:
$N \equiv 4 \equiv -1(mod 5)$
$N \equiv 8 \equiv -1(mod 9)$
$N \equiv 7 \equiv -1(mod 8)$
$N \equiv 6 \equiv -1(mod 7)$

Se llega a que $N \equiv -1 \equiv 2519 (mod 2520)$ por lo tanto no hay solución.


En el caso de:
$N \equiv 4 (mod 5)$
$N \equiv 8 (mod 9)$
$N \equiv 7 (mod 8)$
$N \equiv 5 (mod 7)$

Se llega a que $N \equiv 719 (mod 2520)$ cumple


En el caso de:
$N \equiv 4 \equiv (mod 5)$
$N \equiv 5 \equiv (mod 9)$
$N \equiv 7 \equiv (mod 8)$
$N \equiv 6 (mod 7)$

$N \equiv 2399 (mod 2520)$ no cumple


En el caso de:
$N \equiv 4 \equiv (mod 5)$
$N \equiv 5 \equiv (mod 9)$
$N \equiv 7 \equiv (mod 8)$
$N \equiv 6 (mod 7)$

$N \equiv 1679 (mod 2520)$ cumple


En el caso de:
$N \equiv 4 \equiv (mod 5)$
$N \equiv 5 \equiv (mod 9)$
$N \equiv 7 \equiv (mod 8)$
$N \equiv 4 (mod 7)$

$N \equiv 599 (mod 2520)$ cumple

Por lo tanto, hay $4$ números mas que cumplen lo cual nos deja con un total de $\boxed{2380}$ que cumplen las condiciones.
@Bauti.md ig
Math: Mental Abuse To Human
Responder