FOFO 7 años Problema 7

Problemas que aparecen en el Archivo de Enunciados.
tuvie

Colaborador-Varias OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Jurado-OFO 2017
FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 OFO - Jurado-OFO 2021 OFO - Jurado-OFO 2022
Mensajes: 629
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 14
Nivel: Exolímpico

FOFO 7 años Problema 7

Mensaje sin leer por tuvie »

Dado un entero positivo [math], se dice que [math] es fofeable si, al reemplazar [math] sucesivamente por [math], donde [math] es el primo más grande que satisface [math], se obtiene el [math]. Por ejemplo el [math] es fofeable ya que [math] pero el [math] no ya que [math]. Demostrar que entre los primeros [math] enteros positivos, hay entre [math] y [math] números fofeables.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: FOFO 7 años Problema 7

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Parte [math]: Ver que no hay dos números consecutivos fofeables
Si [math] es fofeable, entonces [math] no es fofeable. Cuando aplicamos el procedimiento con [math], tenemos dos posibles situaciones.
En algún momento antes del último paso llegamos a un primo, lo que nos lleva a [math], entonces [math] no es fofeable.
No llegamos nunca a un primo antes del último paso, entonces en cada paso le restamos el mismo número que a [math], por lo que en el último paso llegamos a [math], que es primo, lo que nos lleva a [math], entonces [math] no es fofeable.
Por lo tanto, si [math] es la cantidad de números fofeables hasta [math], entonces [math]. Notemos que hay grupos de [math] números consecutivos no fofeables (por ejemplo [math], [math] y [math]), entonces [math]


Parte [math]: Ver que en cualquier grupo de [math] números consecutivos hay al menos uno fofeable.
Sea [math] la suma de todos los números que le restamos a [math]. [math] es fofeable si [math]. Si [math] es fofeable entonces [math], pero [math], entonces [math], entonces [math] es fofeable.

Vamos a demostrar por inducción fuerte que en cualquier grupo de [math] números consecutivos (comenzando en [math]) al menos uno es fofeable.

Sea [math] un número fofeable y [math]. Supongamos como hipótesis inductiva que en cualquier grupo de [math] números consecutivos hasta [math] hay al menos uno fofeable (se cumple para algún caso ya que los números [math] son fofeables). Si [math] es fofeable entonces se sigue cumpliendo que en cualquier grupo de [math] números consecutivos (comenzando en [math]) hay al menos uno fofeable (podemos armar los grupos [math] y [math] por ejemplo, que con certeza contendrán un [math]). Supongamos que ninguno de [math] es fofeable, entonces ninguno de [math] puede ser primo, ya que si [math] es primo entonces [math] es fofeable. Como no hay dos primos consecutivos (ya que [math]); [math]; entonces [math]. Entonces al aplicar la operación nos quedan los números [math]. Que son [math] números consecutivos menores que [math], por lo que alguno de ellos es fofeable, entonces alguno de [math] es fofeable, y claramente uno de ellos es [math]. Esto completa la inducción.

Por lo tanto, si [math] es la cantidad de números fofeables hasta [math], entonces [math]. Notemos que hay grupos con más de un número fofeable (por ejemplo [math] y [math] están en el mismo grupo y son fofeables), entonces [math]


De lo demostrado en las dos partes se tiene que si [math] es la cantidad de números fofeables hasta [math], entonces [math].
En particular hasta [math] hay [math]
Por lo tanto, entre los primeros [math] enteros positivos hay entre [math] y [math] números fofeables.
♪♫ do re mi función lineal ♪♫
jujumas

OFO - Mención-OFO 2015 OFO - Medalla de Plata-OFO 2016 FOFO 6 años - Medalla Especial-FOFO 6 años OFO - Oro perfecto-OFO 2017 FOFO Pascua 2017 - Medalla-FOFO Pascua 2017
FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2018 FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 2019
FOFO 9 años - Jurado-FOFO 9 años OFO - Jurado-OFO 2020 COFFEE - Jurado-COFFEE Ariel Zylber
Mensajes: 402
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 13
Nivel: Exolímpico

Re: FOFO 7 años Problema 7

Mensaje sin leer por jujumas »

Parte [math]: Ver que en cualquier grupo de [math] números consecutivos hay al menos uno fofeable.
Spoiler: mostrar
Esto es mentira. Por ejemplo, [math], [math], [math] y [math] son todos no fofeables.
Solución:
Spoiler: mostrar
Notemos trivialmente que [math] es fofeable, y que [math] es fofeable si y sólo si [math] es fofeable.

Para ver la segunda afirmación, notemos que si [math] es fofeable, quiere decir que al restarle repetidas veces [math] obtenemos al número [math]. Al restarle [math] la primera vez, obtenemos entonces que si a [math] le aplicamos esta operación repetidas veces, eventualmente llegaremos a [math], por lo que [math] es fofeable.
Además, si [math] no es fofeable, al aplicarle la operación suficientes veces, eventualmente llegaremos a [math], por lo que al aplicarle la operacíón la primera vez llegaremos a [math] y [math] será no fofeable.

Por cuestiones de definición, vamos a decir además que el [math] es no fofeable.

Lema 1: No existen dos enteros positivos consecutivos fofeables.

Demostración: Supongamos que existen. Sean entonces [math] el menor entero positivo tal que [math] y [math] son fofeables, notemos que el mayor primo menor o igual a [math] es el mismo que el mayor primo menor o igual a [math], ya que sino [math] sería primo y no fofeable. Sea entonces [math] este primo, tenemos que tanto [math] como [math] son fofeables, lo que contradice la minimalidad de [math], ya que [math] no puede ser [math] y para todo [math] mayor a [math], [math] es mayor a [math].


Luego, agrupando los números del [math] al [math] en parejas de enteros consecutivos, obtenemos que hay [math] parejas de enteros consecutivos en donde a lo sumo un entero es fofeable, por lo que existen a lo sumo [math] enteros positivos fofeables.

Para optimizar ahora las cota por arriba, notemos que tanto el [math] como el [math] son no fofeables ([math], [math] y [math], [math]), por lo que al menos una de las [math] parejas de enteros consecutivos no tiene a ningún número fofeable y como mucho hay [math] números fofeables.


Vamos a demostrar ahora que para todo [math] mayor a [math], existen al menos [math] números fofeables entre [math] y [math]. Para ver esto, supongamos que existe [math] tal que entre [math] y [math] la proporción de números fofeables en el rango entre [math] y [math] es menor a [math] tomemos el menor de estos [math]. Es fácil checkear a mano viendo si los primeros números son fofeables o no, que [math] tiene que ser mayor a [math]. Sean [math] entonces todos los primos mayores a [math] y menores a [math], dividamos ahora a los números entre [math] y [math] en los conjuntos [math], en donde [math] contiene los enteros del [math] al [math], [math] los enteros del [math] al [math] para todo [math] entre [math] y [math], y [math] contiene los enteros entre [math] y [math] (es posible que este conjunto este vacío).

Notemos que como la proporción de números fofeables entre [math] y [math] es menor a [math], la proporción de números fofeables en alguno de los [math] también debe serlo. Luego, separemos en casos según cual sea el conjunto que cumple esto.

Veamos que el conjunto [math] no puede cumplir esto, ya que entre los enteros positivos [math], [math], [math] y [math], el [math] es fofeable.

Si el conjunto [math] cumple esto, con [math] entre [math] y [math], tenemos que (usando que [math] es fofeable si y solo si [math] es fofeable, y que tanto [math] como [math] son fofeables) el conjunto de números entre [math] y [math] tiene proporción de números fofeables menor a [math], lo que contradice la minimalidad de [math]. Absurdo.

Si el conjunto [math] cumple esto, tenemos que el conjunto de números entre [math] y [math] tiene proporción de números fofeables menor a [math], por lo que añadiendo el [math], que no es fofeable, a este conjunto, tenemos que la proporción de números fofeables en el conjunto de números entre [math] y [math] es también menor a [math].


Luego, tenemos en particular que entre [math] y [math] hay al menos [math] números fofeables, y como [math] no es fofeable, tenemos que entre [math] y [math] hay al menos [math] números fofeables, lo que implica lo pedido.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: FOFO 7 años Problema 7

Mensaje sin leer por Gianni De Rico »

jujumas escribió:
Parte [math]: Ver que en cualquier grupo de [math] números consecutivos hay al menos uno fofeable.
Spoiler: mostrar
Esto es mentira. Por ejemplo, [math], [math], [math] y [math] son todos no fofeables.
Ups, en la solución me faltó aclarar lo que digo abajo, que siempre me refiero a
Spoiler: mostrar
en cualquier grupo de [math] números consecutivos (comenzando en [math]) al menos uno es fofeable.
Viendo tu ejemplo
Spoiler: mostrar
El [math] está en el grupo [math], y tenemos que [math] es fofeable ya que [math]
En el grupo [math], tenemos que [math] es primo, por lo tanto [math] es fofeable
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Violeta

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

Re: FOFO 7 años Problema 7

Mensaje sin leer por Violeta »

Spoiler: mostrar
Vamos a probar que de cada 2 números consecutivos, como mucho 1 es fofeable y que para cada entero positivo [math], si [math] es la cantidad de enteros menores o iguales a n que son fofeables, [math], para todo número no-primo y [math], para [math] primo.

Vamos a llamar "fofear un número" cuando le restamos el mayor primo menor o igual que el número. Llamamos [math] o [math] al mayor primo menor o igual que [math].

Consideremos la pareja (1,2). Si fofeamos el 2, obtenemos 0 y se cumple que en la pareja (1,2), como mucho un número es fofeable. Ahora asumamos que en toda pareja [math] hay como mucho un numero fofeable, para [math]. Ahora consideremos la pareja [math]. Si o [math] o [math] son primos, acabamos. Si no, digamos [math], para cierto [math]. Es obvio que [math], ya que [math]. Ahora fofeamos [math] y [math] y obtenemos [math]. Pero como [math], por hipótesis, uno de esos dos no es fofeable, de donde o [math] o [math] no es fofeable y esto completa la inducción.

Si ahora consideramos las parejas [math], tenemos que como mucho la mitad de esos números son fofeable. Para ver que es estríctamente menos que la mitad, solo falta encontrar una pareja en que nigún número sea fofeable, como lo es [math]. En fin, [math].

Ahora la parte díficil.

Primero probaremos que [math] es mayor o igual que [math] para [math] y que [math] para [math].

[math].

Ahora asumamos que para todo [math] se verifica que o [math] para [math] no-primo y que para todo [math] primo, [math]

Caso [math] primo:

Como [math] no es primo, porque no es posible tener dos primos consecutivos (excepto el 2 y el 3), tenemos que [math], ya que tenemos que [math] por hipótesis y que [math] porque [math] no es fofeable, por ser primo.

Caso [math] no primo:

Sea [math] Y consideremos el rango de números del [math] a [math] y de [math] a [math] por separados. En el primero rango, hay [math] números y por hipótesis [math]. En los números de [math] a [math], hay [math] números y si los fofeamos todos, obtenemos los números del [math] al [math], de donde hay [math] números fofeables en el rango [math] a [math]. Pero, aún si [math] es primo o no, [math]. Ahora sumamos este resultado con el otro (Es sabido que si [math], pues [math]) Se obtiene [math]. El numerador de esto ya vimos es [math], de donde se obtiene, [math], como queríamos probar.

Ahora bien, como [math], sigue que [math], específicamente, [math], que es lo que se nos pedía.
1  
Para todo [math], existen [math] primos en sucesión aritmética.
Responder