Torneo de las Ciudades - Octubre 2019 - NJ P1

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

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 356
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Torneo de las Ciudades - Octubre 2019 - NJ P1

Mensaje sin leer por Joacoini » Sab 02 Nov, 2019 7:09 pm

Para cada entero $n >1$ llamamos complejidad de $n$ a la cantidad de factores primos que tiene $n$. Por ejemplo, la complejidad de $4$ es igual a $2$ y la complejidad de $6$ es igual a $2$.
a) Hallar todos los $n$ tales que todos los enteros comprendidos estrictamente entre $n$ y $2n$ tienen complejidad menor o igual que la complejidad de $n$.
b) Hallar todos los $n$ tales que todos los enteros comprendidos estrictamente entre $n$ y $2n$ tienen complejidad menor que la complejidad de $n$.
NO HAY ANÁLISIS.

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: 964
Registrado: Dom 17 Oct, 2010 4:44 pm
Medallas: 7
Nivel: Exolímpico

Re: Torneo de las Ciudades - Octubre 2019 - NJ P1

Mensaje sin leer por Matías V5 » Sab 11 Ene, 2020 11:43 am

Spoiler: mostrar
a) Observemos que, dado cualquier entero positivo $k$, el menor número que tiene complejidad $k$ es $2^k$, pues no hay primos menores que $2$. Esto nos dice que si hay alguna potencia de $2$ comprendida estrictamente entre $n$ y $2n$, entonces el número $n$ no cumple la condición pedida, pues dicha potencia de $2$ tendrá complejidad estrictamente mayor que la complejidad de $n$.
La única forma de que no haya ninguna potencia de $2$ comprendida estrictamente entre $n$ y $2n$ es que el propio $n$ sea una potencia de $2$. Si $n = 2^k$, como el menor número que tiene complejidad mayor que $k$ es $2^{k + 1} = 2n$, todos los números comprendidos estrictamente entre $n$ y $2n$ tienen complejidad menor o igual que la complejidad de $n$, como queríamos.
Luego las potencias de $2$ son los únicos números que cumplen la condición pedida.

b) Probaremos que ningún $n$ cumple esta nueva condición. Es claro que esta nueva condición implica la de a), luego, en caso de haber algún $n$ que la cumpla debería ser una potencia de $2$. Sin embargo, para $n = 2^k$ podemos considerar el número $x = 3 \cdot 2^{k – 1}$, que tiene la misma complejidad que $n$ y está comprendido estrictamente entre $n = 2 \cdot 2^{k – 1}$ y $2n = 4 \cdot 2^{k – 1}$.
Entonces no hay soluciones, como habíamos afirmado. $\blacksquare$
We gave you a start so you'd know what to do
You've seen how it works, now it's over to you (...)
For there's so much more to explore!

Numberblocks - https://www.youtube.com/watch?v=SoRiOoqao5Y

Responder