FOFO 7 años Problema 7

tuvie

Colaborador OFO - Medalla de Oro FOFO 6 años - Medalla Especial OFO - Jurado
Mensajes: 539
Registrado: Dom 09 Sep, 2012 11:58 am
Medallas: 5
Nivel: Exolímpico

FOFO 7 años Problema 7

Mensaje sin leer por tuvie » Vie 13 Oct, 2017 2:58 pm

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
Mensajes: 417
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario

Re: FOFO 7 años Problema 7

Mensaje sin leer por Gianni De Rico » Mar 17 Oct, 2017 10:00 am

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.
[math]

jujumas

OFO - Mención OFO - Medalla de Plata FOFO 7 años - Medalla Especial OFO - Oro perfecto FOFO Pascua 2017 - Medalla
Mensajes: 314
Registrado: Dom 26 Oct, 2014 8:30 pm
Medallas: 6
Nivel: 2

Re: FOFO 7 años Problema 7

Mensaje sin leer por jujumas » Mar 17 Oct, 2017 10:56 am

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
Mensajes: 417
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario

Re: FOFO 7 años Problema 7

Mensaje sin leer por Gianni De Rico » Mar 17 Oct, 2017 11:15 am

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
[math]

Avatar de Usuario
Violeta

OFO - Mención FOFO 7 años - Medalla Especial
Mensajes: 323
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 2
Ubicación: Puerto Rico

Re: FOFO 7 años Problema 7

Mensaje sin leer por Violeta » Mié 18 Oct, 2017 2:45 pm

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