Problema 1 Nivel 3 Nacional OMA 2001

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

Colaborador OFO - Jurado
Mensajes: 562
Registrado: Dom 17 Oct, 2010 10:28 pm
Medallas: 3
Nivel: Exolímpico

Problema 1 Nivel 3 Nacional OMA 2001

Mensaje sin leer por Nacho » Sab 15 Sep, 2012 8:57 pm

Sergio piensa un número entero positivo [math], menor o igual que [math]. Iván debe adivinar el número que pensó Sergio, utilizando el siguiente procedimiento: en cada paso, elige dos números enteros positivos [math] y [math] menores que [math], y le pregunta a Sergio cuál es el máximo común divisor entre [math] y [math]. Dar una secuencia de siete pasos que le asegure a Iván adivinar el número [math] que pensó Sergio.

Aclaración: En cada paso, Sergio responde correctamente la pregunta de Iván.
1  
"Though my eyes could see I still was a blind man"

Avatar de Usuario
Guty
Mensajes: 125
Registrado: Mié 17 Oct, 2012 3:48 pm
Nivel: Exolímpico
Ubicación: Munro, Buenos Aires

Re: Problema 1 Nivel 3 Nacional OMA 2001

Mensaje sin leer por Guty » Sab 08 Jun, 2013 12:32 am

Primero, por dónde se me ocurrió encararlo:
Spoiler: mostrar
Lo que me llevó a pensar por dónde podía venir la idea para resolverlo fue que en el enunciado, [math] y que tenemos sólo [math] pasos para llegar a adivinar el número. Como [math] y [math] se me vino a la cabeza que la solución debía andar por ahí (por ahí hay otra más simple, no sé).
Ahora sí la solución:
Spoiler: mostrar
Notemos que al factorizar un número, éste es de la forma: [math] donde [math] es [math] (O sea, que [math] es la mayor potencia de 2 que divide al número y [math] es el producto de todos los factores primos del número que no son [math]). Ahora, veamos qué ocurre al sumar [math] al número:

[math]. como [math] es [math] entonces [math] es [math], de acá que [math] para algún [math] (que no necesariamente es impar). Entonces tenemos que:

[math]

Entonces, al sumar la mayor potencia de 2 que divide al número (llamémosla [math]), obtenemos un número divisible por una potencia de 2 más grande (por lo menos [math]).

Sabiendo ésto hacemos el siguiente procedimiento: En el Paso 1 preguntamos por [math] (O sea, que [math] y [math], de ahora en adelante se dará por entendido cuál es [math] y cuál es [math]), si la respuesta es [math] preguntamos por el [math], con [math] respectivamente en cada caso (porque el [math] entre un número y [math] será la mayor potencia que divida al número hasta [math]), en el Paso 2 preguntamos por el [math], donde [math] es la mayor potencia de 2 que divide a [math], y así, repitiendo estos pasos, nos aseguramos que como mucho en el Paso 6 tenemos un número de la forma [math] tal que [math]. Entonces tenemos 2 cursos a seguir:

CASO 1: Si en algún momento nos respondieron que [math] entonces en el paso siguiente preguntamos [math]. Si la respuesta es [math] entonces [math], si es [math], entonces [math] [math]

CASO 2: Si en algún momento nos respondieron que [math] entonces en el paso siguiente preguntamos [math]. Si la respuesta es [math] entonces [math], si la respuesta es [math] entonces [math] [math]. Notemos que el valor de [math] lo vamos dando nosotros así que podremos despejar.

[math] Nuestro valor de [math] que vamos dando va desde [math] hasta [math], entonces al máximo [math] que podremos llegar será [math], entonces hay dos valores para [math] donde [math], que son [math] y [math]

[math] Los únicos números entre [math] y [math] tales que [math] son [math] y [math], ojo ([math] y [math], pero el [math] en ese caso da [math]).

De esta forma nos aseguramos en como mucho siete pasos adivinar el número [math] que pensó Sergio.

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 417
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario

Re: Problema 1 Nivel 3 Nacional OMA 2001

Mensaje sin leer por Gianni De Rico » Mié 18 Oct, 2017 11:37 pm

Spoiler: mostrar
En el primer paso Iván elige [math], entonces [math]. Conociendo [math] en [math], en el paso [math] Iván elige [math] y [math]. Afirmo que de esta forma Iván puede conocer el resto de [math] en la división por [math]
En efecto, como [math], entonces solo puede ser [math]. Si [math] entonces [math], sino [math]. En cualquier caso, Iván conoce el resto de [math] en la división por [math]. Entonces después del paso [math] Iván conoce el resto de [math] en la división por [math]
Como [math], tenemos que [math]. Si [math] entonces [math], por lo que [math]. Si [math] entonces [math] es múltiplo de [math], como el único múltiplo de [math] en [math] es [math] entonces [math]. Por lo que Iván ya sabe el valor de [math] y no importa cuál sea su última pregunta
Si [math] entonces Iván elige [math] y [math]. Si [math] entonces [math] (ya que el único múltiplo de [math] en [math] es [math]), sino [math]
Si [math] o [math] entonces Iván elige [math] y [math]. Vemos que [math] y [math]; y vemos que [math] y [math], entonces Iván puede conocer el valor de [math].

Queda demostrado que con esta secuencia de pasos Iván puede conocer con certeza el número que pensó Sergio.
[math]

Responder