ONEM 2018 Cuarta Fase Nivel 1 (Problema 3)

Problemas que aparecen en el Archivo de Enunciados.
Rafaga
Mensajes: 12
Registrado: Mar 19 Dic, 2017 6:39 pm
Nivel: Ñandú

ONEM 2018 Cuarta Fase Nivel 1 (Problema 3)

Mensaje sin leer por Rafaga »

Un entero positivo es llamado favorable si tiene tres divisores positivos distintos cuyo producto es un número de la forma $k^4$, donde $k$ es un entero positivo. Por ejemplo, $144$ es favorable porque tiene tres divisores positivos distintos: $144, 9$ y $1$, cuyo producto es $6^4$. Sea $C$ el conjunto de todos los divisores positivos del número $2310^9$. Determine cuántos elementos de $C$ son favorables.

Fedex

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 COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021
Mensajes: 154
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 7
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: ONEM 2018 Cuarta Fase Nivel 1 (Problema 3)

Mensaje sin leer por Fedex »

Spoiler: mostrar
Sea un $n$ favorable y $d_1, d_2, d_3$ los divisores que multiplicados verifican la condición. Notemos que en la factorización de $d_1d_2d_3$ no puede aparecer $p$ tal que $v_p(n) = 1$ ya que en ese caso $1 \leq v_p(d_1d_2d_3) \leq 3$ que no es posible ya que $4 | v_p(d_1d_2d_3)$.

Un primo $p$ es $n$-lindo si $v_p(n) \geq 2$, entonces solo pueden aparecer este tipo de primos en la factorización de $d_1d_2d_3$.

Sea $L_n$ el conjunto de las potencias $p^{v_p(n)}$ donde $p$ es $n$-lindo:
- Si $|L_n| = 0$, $n$ no es favorable.
- Si $|L_n| = 1$ y el elemento que aparece es de la forma $p^2$ entonces la única posibilidad es $p^{0+1+2} = p^3$, entonces $n$ no es favorable. Si es $p^{\alpha}$ para $\alpha \geq 3$ entonces $n$ es favorable, tomando $p^0, p^1, p^3$, ganamos.
- Si $|L_n| \geq 2$ entonces $n$ es favorable, tomando $p^2, q^2, (pq)^2$, ganamos.

Ahora $2310^9 = (2.3.5.7.11)^9$
Como vimos, con que exista $p$ tal que $p^3 | n$, $n$ es favorable.
La cantidad de $n | 2310^9$ que satisfacen esto es:
$\tau(2310^9) - \tau(2310^2) = 10^5 - 3^5$

Si no existe este, es necesario y suficiente que $|L_n| \geq 2$.
La cantidad de $n | 2310^2$ que NO satisfacen esto son:
$\tau(2310) + 5 . \tau(p_1p_2p_3p_4) = 2^5 + 5. 2^4$
(Ese segundo término sale de armar $n$ de la siguiente forma: elegimos uno de los primos ($p_5$) y le damos valuación $2$, mientras que el otro factor es un divisor de $p_1p_2p_3p_4$)
Es decir, favorables son: $\tau(2310^2) - 2^5 - 5. 2^4 = 3^5 - 2^5 - 5. 2^4$

Luego el resultado buscado es:
$10^5 - 3^5 + 3^5 - 2^5 - 5.2^4 = 99888$
This homie really did 1 at P6 and dipped.

Responder