17° Ronda Final Mateclubes P3N5

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Martín Vacas Vignolo
Mensajes: 404
Registrado: Mié 15 Dic, 2010 6:57 pm
Nivel: Exolímpico

17° Ronda Final Mateclubes P3N5

Mensaje sin leer por Martín Vacas Vignolo »

Alexis piensa un número natural $n$ menor o igual a $100$. Brenda juega a averiguar cuál es. En cada ronda del juego Brenda elige un número natural $m$ menor o igual a $100$, Alexis calcula el máximo común divisor de $m$ y $n$ y se lo dice a Brenda. Brenda gana cuando sabe cuál es el número que pensó Alexis. ¿Cuántas rondas necesita Brenda como mínimo para asegurarse ganar?
[math]
fedeq

OFO - Mención-OFO 2015
Mensajes: 30
Registrado: Mié 03 Jul, 2013 7:18 pm
Medallas: 1
Nivel: 1

Re: 17° Ronda Final Mateclubes P3N5

Mensaje sin leer por fedeq »

Ahí esta lo que me dió, queria saber si esta bien
Spoiler: mostrar
26 preguntas como máximo
Matías

OFO - Medalla de Bronce-OFO 2016 OFO - Medalla de Bronce-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017 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 COFFEE - Mención-COFFEE Ariel Zylber
Mensajes: 206
Registrado: Mar 06 Oct, 2015 7:59 pm
Medallas: 8
Nivel: 3

Re: 17° Ronda Final Mateclubes P3N5

Mensaje sin leer por Matías »

Spoiler: mostrar
Supongamos que $n=1$. De ser así, Brenda tiene que ver que ninguno de los primos menores a $100$ divide a $n$, entonces por cada uno de los $25$ primos menores a $100$ ($2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, $37$, $41$, $43$, $47$, $53$, $59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$ y $97$) en alguna ronda Brenda tiene que elegir un $m$ divisible por ese primo. Ahora bien, Brenda no puede elegir un $m$ divisible por dos primos mayores a $10$ (ya que $m\leq 100$); por lo que concluimos que Brenda necesita al menos $21$ rondas (una por cada primo $10<p<100$) para asegurarse ganar.

Ahora vamos a demostrar que con a lo sumo $21$ rondas Brenda puede determinar el valos de $n$:
Supongamos que en las primeras $11$ rondas Brenda elige los siguientes valores de $m$: $77=7\times 11$, $65=13\times 5$, $51=17\times 3$, $38=19\times 2$, $23$, $29$, $31$, $37$, $41$, $43$ y $47$. Tenemos que por cada primo menor a $50$ en alguna ronda elegimos un $m$ divisible por ese primo, entonces tenemos que:

-Si $dcm(m,n)=1$ para todos los $m$, entonces $n$ es un primo mayor a $50$ y menor a $100$ (si $n$ es divisble por un primo mayor a $50$ entonces es igual a ese primo, ya que $n\leq 100$) o $n=1$. Para saberlo, en las $10$ rondas que quedan vamos a ir preguntando por los $10$ primos $50<p<100$ ($53$, $59$, $61$, $67$, $71$, $73$, $79$, $83$, $89$ y $97$) hasta que obtengamos el valor de $n$. Si en las $10$ rondas obtuvimos que $dcm(m,n)=1$ es porque $n=1$.

-Si $dcm(m,n)>1$ para algunos $m$ ya determinamos qué primos dividen a $n$ (no puede un primo mayor a $50$ dividir a $n$ porque sería $n>100$). Ahora bien, a lo sumo $3$ primos distintos pueden dividir a $n$ (ya que $2\times 3\times 5\times 7=210>100$).
Entonces si $n$ es divisible por un primo $p$, vamos a preguntar por $m=p^k$, siendo $p^k$ la mayor potencia perfecta de $p$ menor o igual a $100$, y así vamos a determinar cuántos factores de $p$ dividen a $n$ (ya que $n$ no puede tener más factores $p$ que $p^k$, por la definición de $p^k$). Si $10<p<50$ no es necesaria esta ronda, ya que $p^2>100\geq n\implies p\mid n \wedge p^2\nmid n$.
De esta manera obtenemos que con a lo sumo $3$ rondas más (ya que a lo sumo $3$ primos distintos dividen a $n$) determinamos el valor de $n$, ya que por cada primo $p$ que divide a $n$ sabemos exactamente cuántos factores de $p$ dividen a $n$.

Por lo tanto concluimos que Brenda necesita como mínimo $21$ rondas para asegurarse ganar.
Responder