OFO 2016 Problema 1

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

Colaborador OFO - Jurado FOFO 6 años - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 809
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

OFO 2016 Problema 1

Mensaje sin leer por Vladislao » Sab 16 Ene, 2016 11:54 pm

Entre todas las fracciones [math] con [math] y [math] enteros positivos tales que [math], hallar la de menor denominador.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

Avatar de Usuario
Vladislao

Colaborador OFO - Jurado FOFO 6 años - Jurado FOFO Pascua 2017 - Jurado
Mensajes: 809
Registrado: Mar 28 Dic, 2010 3:26 pm
Medallas: 6
Nivel: Exolímpico
Ubicación: Córdoba

Re: OFO 2016 Problema 1

Mensaje sin leer por Vladislao » Sab 23 Ene, 2016 11:38 pm

Solución oficial.
Spoiler: mostrar
Supongamos que tenemos una fracción [math] tal que [math]. Como [math] es un entero positivo, podemos reescribir las condiciones como sigue: [math] y [math]. A su vez, como [math] y [math] son enteros positivos, resulta que debe ser [math] y [math]. Ahora bien, notemos que de la primera de esas dos desigualdades surge que [math]. Por lo tanto se cumple que:
[math]
de donde se obtiene que:
[math]
Si ahora multiplicamos por [math] a ambos lados, surge que [math], de donde es [math], y por lo tanto [math]. Es decir, cualquier fracción como la del enunciado satisface [math]. Además, la fracción [math] cumple claramente las condiciones. Por lo tanto, esta es la fracción buscada.
Sea [math] Para todo entero positivo [math] se cumple que [math] es un número primo.

fleschler.ian

OFO - Medalla de Plata OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado
Mensajes: 88
Registrado: Vie 05 Oct, 2012 6:40 pm
Medallas: 6
Nivel: Exolímpico

Re: OFO 2016 Problema 1

Mensaje sin leer por fleschler.ian » Dom 24 Ene, 2016 12:16 am

Spoiler: mostrar
Consideremos las sequencias de Farey [math] definidas por todas las fracciones irreducibles [math] tales que [math] ordenadas de forma creciente.
Es un teorema conocido, que dadas dos fracciones [math] y [math]. Son términos consecutivos en la secuencia de Farey [math] y en ese orden, si y solo sí [math].
Si conseguimos una fracción [math] tal que [math], [math] y [math]. Entonces las fracciones [math], [math] y [math] serán consecutivas en la sucesión de Farey [math]. Entonces no habrá ninguna otra fracción [math] en ese intervalo que cumple lo pedido por el enunciado con [math]. Por lo tanto la fracción [math] sería la buscada, la que tiene menor denominador que cumple la desigualdad pedida.
Hallemos [math] y verifiquemos que se cumplen las igualdades pedidas.
Como [math] y [math]. Entonces [math] que implica [math]. Por lo tanto [math].
Ahora nos falta chequear que [math] y [math] son ambos iguales a [math]. Lo verificamos en una de las dos igualdades, ya que estas son iguales entres sí. [math]. Que era lo que queríamos demostrar.
Podemos verificar también que [math]. Por lo tanto [math], que eso implica que son términos consecutivos en la sucesión de Farey [math].
Por lo tanto queda entonces demostrado que [math] es la fracción con menor denominador que cumple lo pedido.

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
OFO - Medalla de Oro FOFO 8 años - Jurado OFO - Jurado FOFO Pascua 2019 - Jurado
Mensajes: 383
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 10
Nivel: Exolímpico

Re: OFO 2016 Problema 1

Mensaje sin leer por jujumas » Dom 24 Ene, 2016 12:31 pm

Spoiler: mostrar
Notemos que la fracción que buscamos en necesariamente menor a [math]. Para resolver este problema partiremos de un Lema conocido y bastante trivial entre las fracciones cuyo numerador es menor a su denominador, que es que la función entre los enteros positivos [math] es estrictamente creciente para todo constante entero positivo [math] (y en particular, se acerca a [math] al aumentar [math]).

Para resolver el enunciado vamos a solamente considerar un conjunto [math] de las mayores fracciones menores a [math].

Para descartar un valor posible de [math], basta con demostrar que la mayor fracción con dicho denominador contenida en [math] es menor a [math]. Para evitar que esta parte de tanteo sea lo mas corta y efectiva posible, usaremos el lema descrito anteriormente.

Primero, notemos que [math] (que pertenece a [math]) es menor a la cota mínima (basta con probar con la calculadora). De acá, por el lema, obtenemos que la mayor fracción contenida en [math] para cada uno de los valores de [math] entre [math] y [math] no cumple (ninguna fracción con [math] esta en [math]). Esta fracción además es equivalente a [math]. Acá podemos usar el lema dos veces. Primero, para ver que toda fracción con [math] entre [math] y [math] y [math] es mayor o igual a la cota mayor, y toda fracción con [math] entre [math] y [math] y [math] es menor a la cota menor. Luego, podemos concluir que [math]. Si [math], tenemos que la mayor fracción contenida en [math] es [math], que no cumple con la cota menor. Luego, si [math] y [math], tenemos por el lema que la menor de todas estas fracciones es [math], que no cumple. Luego, por Lema, la mayor fracción contenida en [math] para [math] entre [math] y [math] es [math] que es exactamente nuestra cota menor, pero no es mayor a esta. De acá vemos que [math] no puede estar entre [math] y [math]. Volvemos a repetir este proceso una vez más con [math] y logramos descartar nuevamente todos los valores de [math] entre [math] y [math] viendo que entre todas las fracciones en [math] la mayor con [math] entre esos valores por lema es [math] que ya habíamos visto que no cumplía. Luego, [math]. Si [math], tenemos la fracción [math], que es la respuesta al enunciado.

Avatar de Usuario
Emerson Soriano

OFO - Mención OFO - Medalla de Oro OFO - Medalla de Plata OFO - Medalla de Bronce
Mensajes: 795
Registrado: Mié 23 Jul, 2014 10:39 am
Medallas: 4

Re: OFO 2016 Problema 1

Mensaje sin leer por Emerson Soriano » Dom 24 Ene, 2016 1:39 pm

Spoiler: mostrar
Solución Problema 1.

Sabemos perfectamente que [math]. Luego, la desigualdad del problema es equivalente a: [math], por tanto podemos deducir que [math], con [math], es decir, [math], pero esto es equivalente a: [math]. Por lo tanto, [math], donde [math] es un entero tal que [math], de donde [math] que es quivalente a: [math], y según esto deducimos que [math], donde [math], quedando lo siguiente: [math], es decir [math], o sea [math]. También podemos notar que reuniendo las ecuaciones se tiene [math]. Pero como [math], entonces [math]. Por lo tanto, el menor valor que puede tomar [math] es [math] y se consigue con [math] y [math] (que claramente cumple en todas las ecuaciones y desigualdades dadas).

Ahora, debemos encontrar todas las fracciones de la forma [math] tal que [math]. Notemos que [math]. Por lo tanto [math] sólo puede ser [math]. Por lo tanto, la única fracción que cumple es [math].

Olímpico

OFO - Mención
Mensajes: 185
Registrado: Sab 25 Ago, 2012 3:30 pm
Medallas: 1
Nivel: 2

Re: OFO 2016 Problema 1

Mensaje sin leer por Olímpico » Dom 24 Ene, 2016 4:44 pm

Spoiler: mostrar
En primer lugar, [math]. Se quiere minimizar [math], para [math] y [math] naturales. Nótese además que [math] es múltiplo de [math], luego debe haber al menos un múltiplo de [math] entre [math] y [math]

Sea [math], en donde [math] el cociente y [math] el resto de la divisón de [math] por [math]. Si [math], [math], luego [math] es estrictamente menor que [math]. Pero como [math] es el cociente de la división de [math] por [math], el siguiente múltiplo de [math] es estrictamente mayor que [math] y por ende estrictamente mayor a [math], lo que es absurdo. Luego es necesario que [math].

Se analizará ahora la ecuación [math]. Se puede ver que se cumple que [math], [math], [math], [math], [math], [math] y [math]. Además, [math] y por otra parte, si [math]. Como es cierto para [math] y si es cierto para [math] lo es para [math], por inducción cada siete números los restos se repiten.

Supóngase [math]. Entonces [math] es múltiplo de [math], luego el anterior múltiplo de [math], llámesele [math], es [math]. Si [math], entonces [math], luego no hay un múltiplo de [math] entre [math] y [math], absurdo. En consecuencia, se descarta [math] para todo [math] menor que [math].
Si [math], [math]. Por lo visto anteriormente, [math] para números de la forma [math], [math] natural. El menor de estos números que cumple [math] es para [math], [math].
Si [math], entonces [math] es al menos [math] (el siguiente posible resto) y [math] es mayor que [math]. No sería mínimo.

Entonces la respuesta es [math] y funciona para [math].

Responder